[BaekJoon] 백준 - 이차열 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

 

 

 

 

풀이: 

처음 숫자를 입력받아 행, 열 계산을 나누어 배열을 재구성하는 문제

클래스를 하나 만들어서 compareTo 를 설정해서 정렬해주었다. 

 

정렬한 이후에는 배열의 사이즈를 재설정해주면 된다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int r;
    static int c;
    static int k;
    static int[][] Array;
    
    static class Number implements Comparable<Number> {
        int n;
        int count;
        
        public Number(int n, int count) {
            this.n = n; this.count = count;
        }
        
        @Override
        public int compareTo(Number o) {
            if (this.count == o.count) {
                return this.n - o.n;
            }
            
            return this.count - o.count;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String[] tmp = br.readLine().split(" ");
        r = Integer.parseInt(tmp[0]);
        c = Integer.parseInt(tmp[1]);
        k = Integer.parseInt(tmp[2]);
        
        Array = new int[100][100];
        for(int i = 0; i<100; i++) {
            for(int j = 0; j<100; j++) {
                Array[i][j] = 0;
            }
        }
        
        for(int i = 0; i<3; i++) {
            String[] s = br.readLine().split(" ");
            Array[i][0] = Integer.parseInt(s[0]);
            Array[i][1] = Integer.parseInt(s[1]);
            Array[i][2] = Integer.parseInt(s[2]);
        }
        
        int time = 0;
        int R = 3; int C = 3;
        while(time <= 100) {
            if (Array[r-1][c-1] == k) {
                break;
            }
            
            if (R >= C) {
                for(int i = 0; i<R; i++) {
                    List<Number> numbers = new ArrayList<>();
                    Map<Integer, Integer> map = new HashMap<>();
                    int size = 0;
                    
                    for(int j = 0; j<C; j++) {
                        if (Array[i][j] == 0) continue;
                        if (!map.containsKey(Array[i][j])) {
                            map.put(Array[i][j], 1);
                        } else {
                            map.put(Array[i][j], map.get(Array[i][j]) + 1);
                        }
                    }
                    
                    for(Integer key: map.keySet()) {
                        numbers.add(new Number(key, map.get(key)));
                    }
    
                    Collections.sort(numbers);
                    
                    for(int j = 0; j<100; j+= 2) {
                        if (j/2 < numbers.size()) {
                            Array[i][j] = numbers.get(j/2).n;
                            Array[i][j+1] = numbers.get(j/2).count;
                        } else {
                            if (size == 0) size = j;
                            Array[i][j] = 0;
                            Array[i][j+1] = 0;
                        }
                    }
                    
                    C = Math.max(C, size);
                }
            } else {
                for(int i = 0; i<C; i++) {
                    List<Number> numbers = new ArrayList<>();
                    Map<Integer, Integer> map = new HashMap<>();
                    int size = 0;
                    
                    for(int j = 0; j<R; j++) {
                        if (Array[j][i] == 0) continue;
                        if (!map.containsKey(Array[j][i])) {
                            map.put(Array[j][i], 1);
                        } else {
                            map.put(Array[j][i], map.get(Array[j][i]) + 1);
                        }
                    }
                    
                    for(Integer key: map.keySet()) {
                        numbers.add(new Number(key, map.get(key)));
                    }
                    
                    Collections.sort(numbers);
                    
                    for(int j = 0; j<100; j+= 2) {
                        if (j/2 < numbers.size()) {
                            Array[j][i] = numbers.get(j/2).n;
                            Array[j+1][i] = numbers.get(j/2).count;
                        } else {
                            if (size == 0) size = j;
                            Array[j][i] = 0;
                            Array[j+1][i] = 0;
                        }
                    }
                    
                    R = Math.max(R, size);
                }
            }
            
            time ++;
        }
        
        if (time > 100) {
            time = -1;
        }
        System.out.println(time);
    }
    
    
}