[Algorithm] 백준_17140 이차원 배열과 연산

문제

3*3 배열에서 1초마다 행 개수>= 열 개수일때는 R연산, 행 개수 < 열 개수일때는 C연산을 적용합니다.
각 연산은 행, 열을 기준으로 각 수가 몇 번 나왔는지를 기준으로 오름차순 정렬합니다. 똑같은 수로 등장했을 경우는 작은 수부터 정렬합니다. 정렬 후 가장 큰 행(또는 열)을 기준으로 크기가 커지며 그 부분은 0으로 채워주면 됩니다.
처음 입력받은 A[r][c]가 k와 같아지는 최소 시간을 출력하면 되는 문제입니다. 전체 시간이 100보다 커지면 -1을 출력합니다.

풀이

1. Number class로 해당 숫자와 등장 횟수를 관리합니다.
   Comparable 인터페이스를 구현해 compareTo 메소드로 정렬 기준을 만들어줍니다.
2. while문을 돌면서 total이 100보다 커지면 -1로 바꾸고 종료합니다.
3. map[r-1][c-1] == k여도 종료합니다.
4. 행보다 열이 크거나 같으면 R연산, 아니면 C연산을 수행합니다.
   • R 연산 : 연산 후 값을 저장할 temp[101][101]을 선언, 초기화합니다.
     가장 큰 행의 길이를 저장하기 위해 max 변수에 Integer.MIN_VALUE를 넣어줍니다.
     각 숫자의 등장 횟수를 카운트하기위해 count 배열을 선언합니다. (배열에 있는 수는 100보다 작거나 같은 자연수라고 했으니 count 배열의 길이는 new int[101]로 초기화합니다.)
     ArrayList를 선언해 각 행을 순회하면서 등장 횟수가 0이 아닌 수를 Number객체로 넣습니다.
     그 후에 sort로 정렬합니다. 정렬 후에는 temp 배열에 넣어주고, 초기 배열의 행 크기를 max로 변경해 다시 초기화합니다. 그리고 초기 배열에 temp를 넣어줬습니다.
   • C 연산 : R연산과 동일합니다.
5. 시간을 출력합니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ_17140 {
    static int r;
    static int c;
    static int k;
    static int total = 0;
    static int[][] map;
    static ArrayList<Number> list;

    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 1;
            } else if(this.count == o.count) {
                if (this.n > o.n) {
                    return 1;
                } else {
                    return -1;
                }
            } else {
                return -1;
            }
        }
    }

    static void rOperation() {
        //행 정렬 연산..
        int[][] temp = new int[101][101];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < map.length; i++) {
            int[] count = new int[101];
            list = new ArrayList<>();
            for (int j = 0; j < map[0].length; j++) {
                if (map[i][j] != 0) {
                    count[map[i][j]]++;
                }
            }

            for (int j = 1; j < count.length; j++) {
                if (count[j] != 0) {
                    list.add(new Number(j, count[j]));
                }
            }

            Collections.sort(list); //Number 객체 정렬

            int z = 0;
            for (int j = 0; j < list.size(); j++) {
                temp[i][z] = list.get(j).n;
                temp[i][z+1] = list.get(j).count;
                z += 2;
                max = Math.max(z, max);
            }
        }

        // 행이나 열이 100이 넘는 경우
        if(max > 100) {
            max = 100;
        }

        map = new int[map.length][max];

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                map[i][j] = temp[i][j];
            }
        }
    }

    static void cOperation() {
        //열 정렬 연산..
        int[][] temp = new int[101][101];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < map[0].length; i++) {
            int[] count = new int[101];
            list = new ArrayList<>();
            for (int j = 0; j < map.length; j++) {
                if (map[j][i] != 0) {
                    count[map[j][i]]++;
                }
            }

            for (int j = 1; j < count.length; j++) {
                if (count[j] != 0) {
                    list.add(new Number(j, count[j]));
                }
            }

            Collections.sort(list); //Number 객체 정렬

            int z = 0;
            for (int j = 0; j < list.size(); j++) {
                temp[z][i] = list.get(j).n;
                temp[z+1][i] = list.get(j).count;
                z += 2;
                max = Math.max(z, max);
            }
        }

        // 행이나 열이 100이 넘는 경우
        if(max > 100) {
            max = 100;
        }

        map = new int[max][map[0].length];

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                map[i][j] = temp[i][j];
            }
        }
    }

    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());

        map = new int[3][3];

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        while (true) {
            if (total > 100) {
                total = -1;
                break;
            }

            if (r-1 < map.length && c-1 < map[0].length) {
                if (map[r - 1][c - 1] == k) {
                    break;
                }
            }

            if (map.length >= map[0].length) {
                rOperation();
            } else {
                cOperation();
            }
            total++;
        }

        System.out.println(total);
    }
}