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

SeungBird·2020년 8월 27일
0

⌨알고리즘(백준)

목록 보기
87/401

문제

크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.

  • R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
  • C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 이 값이 100을 넘어가는 경우에는 -1을 출력한다.

예제 입력 1

1 2 2
1 2 1
2 1 3
3 3 3

예제 출력 1

0

예제 입력 2

1 2 1
1 2 1
2 1 3
3 3 3

예제 출력 2

1

예제 입력 3

1 2 3
1 2 1
2 1 3
3 3 3

예제 출력 3

2

예제 입력 4

1 2 4
1 2 1
2 1 3
3 3 3

예제 출력 4

52

예제 입력 5

1 2 5
1 2 1
2 1 3
3 3 3

예제 출력 5

-1

예제 입력 6

3 3 3
1 1 1
1 1 1
1 1 1

예제 출력 6

2

풀이

이 문제는 우선순위 큐를 이용해서 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    static int N;
    static int M;
    static int[][] map = new int[101][101];;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = 3;
        M = 3;
        int r = Integer.parseInt(str[0]);
        int c = Integer.parseInt(str[1]);
        int k = Integer.parseInt(str[2]);

        for(int i=1; i<=N; i++) {
            String[] input = br.readLine().split(" ");
            for(int j=1; j<=M; j++) {
                map[i][j] = Integer.parseInt(input[j-1]);
            }
        }
        int time=0;

        while(true) {
            if(map[r][c]==k)
                break;

            if(time>100) {
                System.out.println(-1);
                return ;
            }

            if(N>=M) {
                solR();
                time++;
            }

            else {
                solC();
                time++;
            }
        }
        System.out.println(time);
    }

    static void solC() {
        int max = -1;

        for(int i=1; i<=M; i++) {
            PriorityQueue<Pair> pq = new PriorityQueue<>();

            for(int j=1; j<=N; j++) {
                int x = map[j][i];
                if(x==0)
                    continue;
                int cnt = 1;

                for(int k=j+1; k<=N; k++) {
                    if (x == map[k][i]) {
                        cnt++;
                        map[k][i]=0;
                    }
                }
                pq.add(new Pair(x, cnt));
                map[j][i]=0;
            }

            int index = 1;
            max = Math.max(max, pq.size());

            while(!pq.isEmpty()) {
                if(index>100)
                    break;
                Pair p = pq.poll();
                map[index][i] = p.num;
                map[index+1][i] = p.cnt;
                index += 2;
            }
        }
        N = max*2;
        if(N>100)
            N=100;
    }

    static void solR() {
        int max = -1;

        for(int i=1; i<=N; i++) {
            PriorityQueue<Pair> pq = new PriorityQueue<>();

            for(int j=1; j<=M; j++) {
                int x = map[i][j];
                if(x==0)
                    continue;
                int cnt =1;

                for(int k=j+1; k<=M; k++) {
                    if (x == map[i][k]) {
                        cnt++;
                        map[i][k]=0;
                    }
                }
                pq.add(new Pair(x, cnt));
                map[i][j]=0;
            }

            int index = 1;
            max = Math.max(max, pq.size());

            while(!pq.isEmpty()) {
                if(index>100)
                    break;
                Pair p = pq.poll();
                map[i][index] = p.num;
                map[i][index+1] = p.cnt;
                index += 2;
            }
        }
        M = max*2;
        if(M>100)
            M=100;
    }

    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 pair) {
            if(this.cnt==pair.cnt)
                return this.num>pair.num ? 1 : -1;
            return this.cnt>pair.cnt ? 1 : -1;
        }
    }
}
profile
👶🏻Jr. Programmer

0개의 댓글