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

고민1. 배열의 크기가 변경되는 부분을 어떻게 처리할지

문제를 풀면서 연산을 적용할 때마다 배열의 크기가 변경되기 때문에 이를 어떻게 처리해 줄지 고민을 했었다.

매번 2차원 배열을 생성할지 아니면 배열이 아닌 ArrayList로 문제를 풀지.

 

근데 문제에서 "행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다." 이 부분에서 2차원 배열의 최대 크기는 100x100임을 알 수 있었다.

---

고민2. 하나의 행 또는 하나의 열에서 나오는 숫자의 종류와 개수를 어떤 자료구조로 카운트 할 것인지

또한, 수의 종류와 개수를 세야 하는데 어떤 자료구조를 써야할지 고민을 했다. 매번 1차원 배열을 생성하여 카운트 해주면 비효율적이라 생각해서 HashMap<숫자, 개수> 구조를 떠올렸는데 구현할수록 더 복잡해진다는 생각이 들어서 1차원 배열로 구현했다.

---

고민3. 어느 인덱스부터 0으로 채울지에 대한 계산

인덱스로 접근 불가능한 Collections에 대해서 인덱스를 사용하고 싶다면 변수를 하나 선언해서 foreach() 문이 끝날때마다 index++를 해주면 된다.

import java.io.*;
import java.util.*;

public class Solution_for_17140 {
    static int r, c, k;
    static int time = 0;
    static int numRow = 3, numCol = 3;

    public static int[][] nums = new int[100][100];

    static class Number implements Comparable<Number> {
        int num;
        int cnt;

        Number(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Number n) {
            if (this.cnt != n.cnt) {
                return this.cnt - n.cnt;
            }
            else 
                return this.num - n.num;
        }
    }

    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()) - 1;
        c = Integer.parseInt(st.nextToken()) - 1;
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 3; j++) {
                nums[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        while (time <= 100) {

            if (nums[r][c] == k) {
                break;
            }

            // 열의 개수 <= 행의 개수 -> R연산
            if (numCol <= numRow) {
                sortR();
            }

            // 행의 개수 < 열의 개수 -> C연산
            else {
                sortC();
            }

            time++;
        }

        System.out.println(100 < time ? "-1" : time);
    }

    // R 연산
    public static void sortR() {
        int newNumCol = 0;
        for (int i = 0; i < numRow; i++) {
            
            int[] count = new int[101];
            for (int j = 0; j < numCol; j++) {
                int num = nums[i][j];
                if (num != 0) count[num]++;
            }

            List<Number> list = new ArrayList<>();
            for (int v = 1; v < 101; v++) {
                if (0 < count[v]) list.add(new Number(v, count[v]));
            }

            Collections.sort(list);

            int idx = 0;
            for (Number n : list) {
                if (100 <= idx) break;
                nums[i][idx++] = n.num;
                if (100 <= idx) break;
                nums[i][idx++] = n.cnt;
            }
            newNumCol = Math.max(newNumCol, idx);

            for (int j = idx; j < 100; j++) {
                nums[i][j] = 0;
            }
        }
        numCol = newNumCol;
    }

    // C 연산
    public static void sortC() {
        int newNumRow = 0;
        for (int j = 0; j < numCol; j++) {
            int[] count = new int[101];
            for (int i = 0; i < numRow; i++) {
                int num = nums[i][j];
                if (num != 0) count[num]++;
            }

            List<Number> list = new ArrayList<>();
            for (int v = 1; v < 101; v++) {
                if (0 < count[v]) {
                    list.add(new Number(v, count[v]));
                }
            }

            Collections.sort(list);

            int idx = 0;
            for (Number n : list) {
                if (100 <= idx) break;
                nums[idx++][j] = n.num;
                if (100 <= idx) break;
                nums[idx++][j] = n.cnt;
            }
            newNumRow = Math.max(newNumRow, idx);

            for (int i = idx; i < 100; i++) {
                nums[i][j] = 0;
            }
        }
        numRow = newNumRow;
    }
}