[ 백준/Java ] 17140. 이차원 배열과 연산

백준 링크 : https://www.acmicpc.net/problem/17140

 

🌱 [ 문제 ]

크기가 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연산도 할 수 있으므로 R연산만 설명 하겠습니다.

 

[ R 연산 과정 ]

[ { 수, 수 등장 횟수 } 구하기 ]

• 수와 수의 등장 횟수를 확인 하기 위해 Map<Integer, Integer> 사용
• 배열을 돌며 0이 아닌 수를 map에 넣습니다.
• Map.Entry를 통해 수와 수의 등장횟수를 꺼냅니다.
• 행의 결과를 저장 하고 정렬 하기 위해 List를 사용
• ( 단. 각 행의 결과를 저장 해야 하기 때문에 중첩 List<List<NumberCount>>를 사용 )
• 행의 연산 결과를 List<NumberCount> 넣고 정렬 합니다.

        List<List<NumberCount>> numberCounts = new ArrayList<>();

        // 초기화
        for(int row = 0; row < arr.length; row++){
            numberCounts.add(new ArrayList<>());
        }

        // 행 정렬
        for(int row = 0; row < arr.length; row++){
            Map<Integer, Integer> countMap = new HashMap<>();

            for(int col = 0; col < arr[0].length; col++){
                if(isZeroNumFromArr(row, col)){
                    continue;
                }
                countMap.put(
                arr[row][col], countMap.getOrDefault(arr[row][col], 0) + 1
                );
            }

            List<NumberCount> rowNumberCounts = numberCounts.get(row);
            for(Map.Entry<Integer, Integer> entry : countMap.entrySet()){
                rowNumberCounts.add(
                new NumberCount(entry.getKey(), entry.getValue())
                );
            }
            Collections.sort(rowNumberCounts);
        }

 

[ 최대 길이 찾기 ]

• 각 행의 List<NumberCount>의 크기를 통해 최대 길이를 찾습니다.
• ( 단. NumberCount는 한쌍이므로 * 2 )
• 최대 길이는 100을 넘을수 없기 때문에 최대 길이와 100중 작은 수를 최대 길이로 선택

	// 최대 길이 찾기
        int maxLength = 0;
        for(List<NumberCount> rowNumberCounts : numberCounts){
            int numberCountsSize = rowNumberCounts.size();
            maxLength = Math.max(maxLength, numberCountsSize * 2);
        }

        // 최대 길이는 100
        maxLength = Math.min(maxLength, MAX_ARRAY_LENGTH);

 

[ 배열 채우기 ]

• 저장한 List<List<NumberCount>>를 통해 배열을 채웁니다.
• (단. 100개가 최대 이므로 예외 처리를 해주어야 합니다. )

	// 배열 채우기
        int[][] nextArr = new int[arr.length][maxLength];
        for(int row = 0; row < nextArr.length; row++){
            List<NumberCount> rowNumberCounts = numberCounts.get(row);

            for(int col = 0; col < rowNumberCounts.size(); col++){
                // 최대 100개 까지
                if(col >= MAX_NUMBERCOUNTS_SIZE){
                    break;
                }

                NumberCount colNumberCount = rowNumberCounts.get(col);
                nextArr[row][col * 2] = colNumberCount.num;
                nextArr[row][col * 2 + 1] = colNumberCount.count;
            }
        }
        return nextArr;

 

[ 전체 코드 ]

public class Main {
    static final int INIT_ROW = 3;
    static final int INIT_COL = 3;
    static final int MAX_TIME = 100;
    static final int MAX_ARRAY_LENGTH = 100;
    static final int MAX_NUMBERCOUNTS_SIZE = 50;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int targetRow = Integer.parseInt(st.nextToken()) - 1;
        int targetCol = Integer.parseInt(st.nextToken()) - 1;
        int targetNum = Integer.parseInt(st.nextToken());

        // 입력 받기
        arr = new int[INIT_ROW][INIT_COL];
        for(int i = 0; i < arr.length; i++){
            arr[i] = Stream.of(br.readLine().split(" "))
            .mapToInt(Integer::parseInt).toArray();
        }

        int time = 0;
        while(time <= MAX_TIME){
            if(isArrayIn(targetRow,targetCol) &&
            	isFindTarget(targetRow, targetCol, targetNum)){
                break;
            }
            if(isRCalculation()){
                arr = RCalculation();
            }
            else{
                arr = CCalculation();
            }
            time++;
        }
        System.out.print(time > MAX_TIME ? -1 : time);
    }

    private static int[][] RCalculation(){
        List<List<NumberCount>> numberCounts = new ArrayList<>();

        // 초기화
        for(int row = 0; row < arr.length; row++){
            numberCounts.add(new ArrayList<>());
        }

        // 행 정렬
        for(int row = 0; row < arr.length; row++){
            Map<Integer, Integer> countMap = new HashMap<>();

            for(int col = 0; col < arr[0].length; col++){
                if(isZeroNumFromArr(row, col)){
                    continue;
                }
                countMap.put(arr[row][col], countMap.getOrDefault(arr[row][col], 0) + 1);
            }

            List<NumberCount> rowNumberCounts = numberCounts.get(row);
            for(Map.Entry<Integer, Integer> entry : countMap.entrySet()){
                rowNumberCounts.add(new NumberCount(entry.getKey(), entry.getValue()));
            }
            Collections.sort(rowNumberCounts);
        }

        // 최대 길이 찾기
        int maxLength = 0;
        for(List<NumberCount> rowNumberCounts : numberCounts){
            int numberCountsSize = rowNumberCounts.size();
            maxLength = Math.max(maxLength, numberCountsSize * 2);
        }

        // 최대 길이는 100
        maxLength = Math.min(maxLength, MAX_ARRAY_LENGTH);

        // 배열 채우기
        int[][] nextArr = new int[arr.length][maxLength];
        for(int row = 0; row < nextArr.length; row++){
            List<NumberCount> rowNumberCounts = numberCounts.get(row);

            for(int col = 0; col < rowNumberCounts.size(); col++){
                // 최대 100개 까지
                if(col >= MAX_NUMBERCOUNTS_SIZE){
                    break;
                }

                NumberCount colNumberCount = rowNumberCounts.get(col);
                nextArr[row][col * 2] = colNumberCount.num;
                nextArr[row][col * 2 + 1] = colNumberCount.count;
            }
        }
        return nextArr;
    }

    private static int[][] CCalculation(){
        List<List<NumberCount>> numberCounts = new ArrayList<>();

        // 초기화
        for(int col = 0; col < arr[0].length; col++){
            numberCounts.add(new ArrayList<>());
        }

        // 열 정렬
        for(int col = 0; col < arr[0].length; col++){
            Map<Integer, Integer> countMap = new HashMap<>();

            for(int row = 0; row < arr.length; row++){
                if(isZeroNumFromArr(row, col)){
                    continue;
                }
                countMap.put(arr[row][col], countMap.getOrDefault(arr[row][col], 0) + 1);
            }

            List<NumberCount> colNumberCounts = numberCounts.get(col);
            for(Map.Entry<Integer, Integer> entry : countMap.entrySet()){
                colNumberCounts.add(new NumberCount(entry.getKey(), entry.getValue()));
            }
            Collections.sort(colNumberCounts);
        }

        // 최대 길이 찾기
        int maxLength = 0;
        for(List<NumberCount> colNumberCounts : numberCounts){
            int numberCountsSize = colNumberCounts.size();
            maxLength = Math.max(maxLength, numberCountsSize * 2);
        }

        // 최대 길이는 100
        maxLength = Math.min(maxLength, MAX_ARRAY_LENGTH);

        // 배열 채우기
        int[][] nextArr = new int[maxLength][arr[0].length];
        for(int col = 0; col < nextArr[0].length; col++){
            List<NumberCount> rowNumberCounts = numberCounts.get(col);

            for(int row = 0; row < rowNumberCounts.size(); row++){
                // 100개 넘을수 있기 때문
                if(row >= MAX_NUMBERCOUNTS_SIZE){
                    break;
                }

                NumberCount colNumberCount = rowNumberCounts.get(row);
                nextArr[row * 2][col] = colNumberCount.num;
                nextArr[row * 2 + 1][col] = colNumberCount.count;
            }
        }
        return nextArr;
    }

    private static boolean isArrayIn(int targetRow, int targetCol) {
        return targetRow <= arr.length -1 && targetCol <= arr[0].length - 1;
    }

    private static boolean isFindTarget(int row, int col, int num){
        return arr[row][col] == num;
    }

    private static boolean isRCalculation(){
        return arr.length >= arr[0].length;
    }

    private static boolean isZeroNumFromArr(int row, int col) {
        return arr[row][col] == 0;
    }

    static class NumberCount implements Comparable<NumberCount>{
        private int num;
        private int count;

        public NumberCount(int num, int count) {
            this.num = num;
            this.count = count;
        }

        @Override
        public int compareTo(NumberCount another){
            int countResult = this.count - another.count;
            if(countResult != 0) return countResult;
            return this.num - another.num;
        }
    }
}