백준 17140번 이차원 배열과 연산

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

public class TwoDimenArrCal {
    static int r;
    static int c;
    static int k;
    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());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        arr = new int[100][100];
        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        boolean R = true; // true면 R, false면 C
        HashMap<Integer,Integer> hashMap = new HashMap<>()// 빈도수 체크
        int row = 3;
        int col = 3;

        List<int[]> list = new ArrayList<>();//숫자,빈도수 정렬을 위한 리스트
        int count = 0;//시간
        while (true){
            if(arr[r-1][c-1]==k){
                System.out.println(count);
                return;
            }
            if(count==100){
                System.out.println(-1);
                return;
            }
            if (R){
                int max = Integer.MIN_VALUE;
                for (int i = 0; i < row; i++) {
                    hashMap.clear();
                    list.clear();
                    for (int j = 0; j < col; j++) {
                        if(arr[i][j]==0) continue;
                        hashMap.put(arr[i][j],hashMap.getOrDefault(arr[i][j],0)+1);
                    }
                    for(int num: hashMap.keySet()){
                        list.add(new int[]{num,hashMap.get(num)});
                    }
                    Collections.sort(list, new Comparator<int[]>() {
                        @Override
                        public int compare(int[] a, int[] b) {
                            return Integer.compare(a[0],b[0]);
                        }
                    });
                    Collections.sort(list, new Comparator<int[]>() {
                        @Override
                        public int compare(int[] a, int[] b) {
                            return Integer.compare(a[1],b[1]);
                        }
                    });

                    int index = 0;
                    for (int j = 0; j < list.size(); j++) {
                        arr[i][index] = list.get(j)[0];
                        index++;
                        arr[i][index] = list.get(j)[1];
                        index++;
                    }
                    if(index<col){
                        for (int j = index; j < col; j++) {
                            arr[i][j] = 0;
                        }
                    }
                    max = Math.max(max,index);

                }
                col = max;
            }else {
                int max = Integer.MIN_VALUE;
                for (int i = 0; i < col; i++) {
                    hashMap.clear();
                    list.clear();
                    for (int j = 0; j < row; j++) {
                        if(arr[j][i]==0) continue;
                        hashMap.put(arr[j][i],hashMap.getOrDefault(arr[j][i],0)+1);
                    }
                    for(int num: hashMap.keySet()){
                        list.add(new int[]{num,hashMap.get(num)});
                    }
                    Collections.sort(list, new Comparator<int[]>() {
                        @Override
                        public int compare(int[] a, int[] b) {
                            return Integer.compare(a[0],b[0]);
                        }
                    });
                    Collections.sort(list, new Comparator<int[]>() {
                        @Override
                        public int compare(int[] a, int[] b) {
                            return Integer.compare(a[1],b[1]);
                        }
                    });

                    int index = 0;
                    for (int j = 0; j < list.size(); j++) {
                        arr[index][i] = list.get(j)[0];
                        index++;
                        arr[index][i] = list.get(j)[1];
                        index++;
                    }
                    if(index<row){
                        for (int j = index; j < row; j++) {
                            arr[j][i] = 0;
                        }
                    }
                    max = Math.max(max,index);

                }
                row = max;

            }
            if(row>=col){
                R = true;
            }
            else {
                R = false;
            }
            count++;
        }

    }
}

풀이방법

전체적인 설계는 100x100 이차원 배열을 생성 후, R,C연산에 따라, 각 행 또는 열을 해쉬맵, 리스트를 통해 정렬을 반복하는 것이다.

1. hashmap에 숫자와 빈도수를 세서 넣는다. 이때, 0은 세지 않는다.
2. 숫자와 빈도수를 list에 전달한다.
3. 📢 리스트를 숫자 기준으로 오름차순 정렬하고, 다시 빈도수 기준으로 정렬한다.
4. 리스트를 탐색하며, 배열에 숫자와 빈도수를 차례로 넣는다.
5. 배열에 0이 아닌 숫자가 들어간 인덱스(index)가 배열의 최대길이(row,col) 보다 작다면, 그 나머지 인덱스는 0으로 채운다.
6. 각 행 또는 열의 0이 아닌 숫자가 들어간 배열의 길이를 Math.max를 통해 갱신한다.
7. 행 보다 열이 작으면 R = false로 바꾸고, 반복을 계속한다.
8. arr[r][c]가 k 거나, count가 100초가 지나면, 반복을 탈출한다.

후기

풀이의 3,4번이 핵심인 문제였다. 배열을 미리 전부 생성해놓고 시작한다던가, 정렬을 2번 한다던가 등의 생각해야하는 조건이 많은 문제였다.