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

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

17140번: 이차원 배열과 연산

 

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 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초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

 

풀이

이 문제는 사실 처음엔 이해하기가 조금 힘들었습니다.

매 초마다 R연산 또는 C연산이 일어납니다. 행개수 >= 열개수 일 때는 R연산, 행개수 < 열개수 일 때는 C연산이 일어납니다.

R연산의 경우엔 가로를 정렬하고 C연산의 경우엔 세로를 정렬합니다.

 

정렬 방식 역시 조금 특이한데, 등장횟수의 오름차순, 등장 횟수가 같다면 수가 커지는 순으로 정렬이 됩니다.

정렬 할 때는 수, 등장횟수를 모두 matrix에 넣어주어야 합니다.

 

import java.util.Scanner;
import java.util.*;

class Pair implements Comparable<Pair> {
	int cnt, num;

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

	public int compareTo(Pair o) {
		if (this.cnt > o.cnt) {
			return 1;
		} else if (this.cnt == o.cnt) {
			return this.num - o.num;
		} else {
			return -1;
		}
	}
}

public class Main {
	static int[][] matrix = new int[101][101];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);


		int r = sc.nextInt();
		r--;
		int c = sc.nextInt();
		c--;
		int k = sc.nextInt();

		int R = 3;
		int C = 3;

		for(int i=0; i<3; i++) {
			for(int j = 0; j<3; j++) {
				matrix[i][j] = sc.nextInt();
			}
		}

		int time = -1;

		for(int l=0; l<=100; l++) {
			if(matrix[r][c] == k) {
				time = l;
				break;
			}

			// R연산 
			if(R>=C) {
				int newC = 0;

				for(int i=0; i<R; i++){
					PriorityQueue<Pair> q1 = new PriorityQueue<Pair>();
					int[] numCnt = new int[101];

					for(int j=0; j<C; j++){

						numCnt[matrix[i][j]]++;
						matrix[i][j] = 0;
					}

					for(int m=1; m<101; m++){
						if(numCnt[m] > 0){

							q1.add(new Pair(numCnt[m], m));
						}
					}

					int index = 0;  

					while(!q1.isEmpty()) {
						//System.out.println(q1.peek().cnt);
						matrix[i][index++] = q1.peek().num;
						matrix[i][index++] = q1.peek().cnt;
						q1.remove();
					}

					//행,열 길이 갱신 (R연산인 경우 열길이만 갱신)
					if(newC < index){
						newC = index;
					}

				}
				C = newC;
			}

			// C연산 
			else {
				int newR = 0;


				for(int i=0; i<C; i++){
					PriorityQueue<Pair> q1 = new PriorityQueue<Pair>();

					int[] numCnt = new int[101];

					for(int j=0; j<R; j++){
						numCnt[matrix[j][i]]++;
						matrix[j][i] = 0;
					}
					for(int m=1; m<101; m++){
						if(numCnt[m] != 0){
							q1.add(new Pair(numCnt[m], m));
						}
					}


					int index = 0;  

					while(!q1.isEmpty()) {
						Pair p = q1.poll();
						matrix[index++][i] = p.num;
						matrix[index++][i] = p.cnt;
					}

					//행,열 길이 갱신 (R연산인 경우 열길이만 갱신)
					if(newR < index){
						newR = index;
					}

				}
				R = newR;
			}

		}
		System.out.println(time);


	}


}