[ 백준 / BOJ 17140 ] 이차원 배열과 연산 ( 자바 / JAVA )

[https://www.acmicpc.net/problem/17140](https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

문제 설명

배열 A : 처음에 3x3인 배열, 인덱스는 1부터 시작
1초가 지날때마다 연산이 적용됨
👉 R연산 : 모든 행에 대해서 정렬 수행, 행의 개수 >= 열의 개수
👉 C연산 : 모든 열에 대해서 정렬 수행, 행의 개수 < 열의 개수

각각의 수가 나타난 횟수의 오름차순으로, 같다면 숫자가 커지는 순으로 정렬해서 배열A에 넣기
행 또는 열의 크기가 100이 넘어가면, 처음 100개만‼️
A[r][c] == k가 되는 최소 시간
100초가 지나도 k가 되지 않으면 -1 출력

문제 풀이

Map<num, cnt> : 숫자들의 갯수
PriorityQueue<pair> : pair(수, 갯수) 저장

operating()

1) xLen >= yLen 👉 R()
2) xLen < xLen 👉 C()

코드

    import javax.swing.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_BOJ_17140_이차원_배열과_연산 {

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

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

        @Override
        public int compareTo(pair o) {
            int result = this.cnt - o.cnt;
            if(result == 0)
                result = this.num - o.num;

            return result;
        }
    }

    static int r, c, k;
    static int[][] A = new int[101][101];
    static int xLen = 3, yLen = 3;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        r = Integer.parseInt(stringTokenizer.nextToken());
        c = Integer.parseInt(stringTokenizer.nextToken());
        k = Integer.parseInt(stringTokenizer.nextToken());

        for (int i = 1; i <= 3; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 1; j <= 3; j++) {
                A[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        System.out.println(solution());

    }

    private static int solution() {
        for (int time = 0; time <= 100; time++) {
            if(A[r][c] == k) return time;

            operating();
        }
        return -1;
    }

    private static void operating() {
        if (xLen >= yLen) {
            for (int i = 1; i <= xLen; i++) R(i);
        } else {
            for (int i = 1; i <= yLen; i++) C(i);
        }

    }

    private static void C(int key) {
        PriorityQueue<pair> pq = new PriorityQueue<>();
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 1; i <= xLen; i++) {
            if(A[i][key] == 0) continue;
            map.compute(A[i][key], (num, cnt) -> cnt == null ? 1 : cnt + 1);
        }
        map.forEach((k, v) -> pq.add(new pair(k, v)));

        int i = 1;
        while (!pq.isEmpty()) {
            pair p = pq.poll();
            A[i++][key] = p.num;
            A[i++][key] = p.cnt;
        }

        xLen = Math.max(xLen, i);

        while (i <= 99) {
            A[i++][key] = 0;
            A[i++][key] = 0;
        }
    }

    private static void R(int key) {
        PriorityQueue<pair> pq = new PriorityQueue<>();
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 1; i <= yLen; i++) {
            if(A[key][i] == 0) continue;
            map.compute(A[key][i], (num, cnt) -> cnt == null ? 1 : cnt + 1);
        }
        map.forEach((k, v) -> pq.add(new pair(k, v)));

        int i = 1;
        while (!pq.isEmpty()) {
            pair p = pq.poll();
            A[key][i++] = p.num;
            A[key][i++] = p.cnt;
        }

        yLen = Math.max(yLen, i);

        while(i <= 99){
            A[key][i++] = 0;
            A[key][i++] = 0;
        }

    }
}