백준 17140번. 이차원 배열과 연산 (Java)

Problem

• 문제 링크

문제에서 설명해주는 R 연산과 C 연산을 반복한 뒤 특정 좌표의 숫자가 k 와 일치하는 시간은 몇 초 뒤인지 구하는 문제입니다.

Solution

단순하게 구현하면 됩니다.

R 연산과 C 연산의 인덱스 빼고는 거의 동일한데 저는 헷갈릴까봐 그냥 각각 정의했습니다.

인덱스에 대한 처리만 주의하면 되는 문제입니다.

특정 행이나 열에 대한 연산은 다음 순서로 진행했습니다.

1. 숫자들의 갯수를 카운팅해서 Map<number, count> 에 저장합니다.
2. 우선순위를 적용한 Pair 클래스에 넣어서 우선순위 큐에 넣어줍니다.
3. 우선순위 큐에서 순서대로 값들을 꺼내 배열을 다시 갱신해주고 해당되지 않는 배열들은 전부 0 으로 초기화해줍니다.

주의할 점

1. R 연산, C 연산 인덱스 헷갈리지 않기

2. 100 초가 넘어가는 순간이기 때문에 100 초에 성공한 값도 인정

3. 연산할 때 0 의 갯수는 세지 않는 예외처리 필요

4. A 배열에 그대로 새 값을 덮어쓴다면 연산에 해당하지 않는 값은 0 으로 세팅 해줘야한다.

   • 연산을 한다고 길이가 무조건 길어지지는 않다.
   • [1, 1, 1, 1, 1] 을 연산하면 [1, 5] 가 되는데 만약 뒤의 값들을 0 으로 바꾸지 않으면 [1, 5, 1, 1, 1] 로 남는다.

Java Code

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

class Main {
    static class Pair implements Comparable<Pair> {
        int number;
        int count;

        Pair(int n, int c) {
            this.number = n;
            this.count = c;
        }

        // count 가 작은 게 앞으로, 같으면 number 가 작은게 앞으로
        public int compareTo(Pair o) {
            if (this.count > o.count) {
                return 1;
            } else if (this.count == o.count) {
                return this.number - o.number;
            } else {
                return -1;
            }
        }
    }

    static int r, c, k;
    static int[][] A = new int[101][101];
    static int xLength = 3, yLength = 3;

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

        // input
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

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

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

        // solution
        System.out.println(solution());
    }

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

        return -1;
    }

    // R 연산 : 배열 A의 모든 행에 대해서 정렬을 수행한다
    // C 연산 : 배열 A의 모든 열에 대해서 정렬을 수행한다
    static void operating() {
        if (xLength >= yLength) {
            for (int i = 1; i <= xLength; i++) {
                R(i);
            }
        } else {
            for (int i = 1; i <= yLength; i++) {
                C(i);
            }
        }
    }

    // 각 숫자들의 개수를 구해서 HashMap 에 담았다가 우선순위 큐에 옮겨담아서 정렬
    static void R(int key) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        Map<Integer, Integer> map = new HashMap<>(); // <number, count>

        for (int i = 1; i <= yLength; i++) {
            if (A[key][i] == 0) continue;
            map.compute(A[key][i], (num, count) -> count == null ? 1 : count + 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.number;
            A[key][i++] = p.count;
        }

        yLength = Math.max(yLength, i);

        while (i <= 99) {
            A[key][i++] = 0; 
            A[key][i++] = 0; 
        }
    }
    
    // 각 숫자들의 개수를 구해서 HashMap 에 담았다가 우선순위 큐에 옮겨담아서 정렬
    static void C(int key) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        Map<Integer, Integer> map = new HashMap<>(); // <number, count>

        for (int i = 1; i <= xLength; i++) {
            if (A[i][key] == 0) continue;
            map.compute(A[i][key], (num, count) -> count == null ? 1 : count + 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.number;
            A[i++][key] = p.count;
        }

        xLength = Math.max(xLength, i);

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