이차원 배열과 연산 17140

LJM·2023년 9월 8일
0

백준풀기

목록 보기
225/259

https://www.acmicpc.net/problem/17140

배열을 동적으로 변경해가면서 짜야하는 줄알고 엄청 복잡하게 짜다가
어차피 100x100 크기를 못벗어나네 그리고 R,C연산 끝날때마다 rowsize, colsize 최대값을 저장하면 되잖아란 생각이 들었다.
그리고 HashMap 으로 숫자, 카운트 이렇게 할필요없이
100개의 숫자 배열로 카운팅하고 그거를 PriorityQueue 에 넣어서정렬하면된다

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

public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int r = Integer.parseInt(st.nextToken()) - 1;
        int c = Integer.parseInt(st.nextToken()) - 1;
        int k = Integer.parseInt(st.nextToken());

        int[][] A = new int[100][100];
        int rowSize = 3, colSize = 3;

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

        int time = 0;
        while (time <= 100) {
            if (A[r][c] == k) {
                System.out.println(time);
                return;
            }

            if (rowSize >= colSize) {
                int maxCol = 0;
                for (int i = 0; i < rowSize; i++) {
                    int[] count = new int[101];
                    for (int j = 0; j < colSize; j++) {
                        if (A[i][j] == 0) continue;
                        count[A[i][j]]++;
                    }

                    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
                    for (int j = 1; j <= 100; j++) {
                        if (count[j] > 0) {
                            pq.add(new int[]{j, count[j]});
                        }
                    }

                    int colIdx = 0;
                    while (!pq.isEmpty()) {
                        int[] cur = pq.poll();
                        A[i][colIdx++] = cur[0];
                        A[i][colIdx++] = cur[1];
                        if (colIdx >= 100) break;
                    }
                    maxCol = Math.max(maxCol, colIdx);
                    for (; colIdx < 100; colIdx++) {
                        A[i][colIdx] = 0;
                    }
                }
                colSize = maxCol;
            } else {
                int maxRow = 0;
                for (int j = 0; j < colSize; j++) {
                    int[] count = new int[101];
                    for (int i = 0; i < rowSize; i++) {
                        if (A[i][j] == 0) continue;
                        count[A[i][j]]++;
                    }

                    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
                    for (int i = 1; i <= 100; i++) {
                        if (count[i] > 0) {
                            pq.add(new int[]{i, count[i]});
                        }
                    }

                    int rowIdx = 0;
                    while (!pq.isEmpty()) {
                        int[] cur = pq.poll();
                        A[rowIdx++][j] = cur[0];
                        A[rowIdx++][j] = cur[1];
                        if (rowIdx >= 100) break;
                    }
                    maxRow = Math.max(maxRow, rowIdx);
                    for (; rowIdx < 100; rowIdx++) {
                        A[rowIdx][j] = 0;
                    }
                }
                rowSize = maxRow;
            }
            time++;
        }
        System.out.println(-1);
    }
}
profile
게임개발자 백엔드개발자

0개의 댓글