[Baekjoon] 이차원 배열과 연산

👀 문제 설명

문제

크기가 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을 출력한다.

 

예제 입력 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

 

✍🏻풀이

구현 문제이다.

먼저, A 배열에 입력을 받는다. 이 때, A 배열은 최대 크기 101 101까지 확장할 수 있으므로, 크기를 101 x 101로 설정해준다.

그리고, rSize와 cSize를 사용해 현재의 행 크기, 열 크기를 입력받는다. 즉, 초기 A 배열의 크기는 3 x 3이므로, rSize = 3, cSize = 3이다.

그리고, while문을 사용해 time이 101이 아닐동안 R 연산 또는 C 연산을 반복한다.

time이 101이라면, 100초동안 배열을 정렬해도, A[r][c] = k가 되지 않았다는 소리이므로, -1을 출력한다.

 

R 연산과 C 연산을 수행하는 메서드는 행과 열의 접근 순서만 다르고, 구현 방식은 같다.

 

R 연산을 예로 들면, 제일 먼저 A 배열을 돌면서 무슨 숫자가 몇 번 나왔는지 저장한다. 이 때, numCount 변수를 사용해 저장해주는데, numCount[2] = 3 이라면 2가 3번 나왔다는 뜻이다. 그리고, 해당 위치의 숫자의 개수를 세어줬으면, A[i][j]를 0으로 바꿔준다.

이유는 다음 그림을 예로 들면, 

A 배열의 초기값은 검은색이고, 1초가 지난 후의 A배열은 빨간색, 2초가 지난 후의 A 배열은 파란색이다.

0초에서 1초로 바뀔 때, (2, 2)의 값을 보면, 1초일 때의 A 배열의 (2, 2)는 정렬로 생긴 값이 아니라 0으로 채워줘야 한다.

즉, A[i][j]를 0으로 바꾸지 않으면, 1초일 때의 A 배열이 0초일 때의 A 배열에 덮어씌워진다는 뜻이다.

numCount를 숫자에 맞게 다 채웠으면, numCount를 확인하면서 numCount[i]가 0이 아닐 경우에, 숫자가 있다는 뜻이므로 ArrayList list에 넣어준다.

 

이 때, NumInfo라는 객체로 넣게 되는데, 이 NumInfo는 배열 정렬을 쉽게 하기 위해 새로 생성한 클래스이다.

NumInfo는 숫자(number)와 몇 번 나왔는지(count) 저장하는 멤버 변수를 갖는데, 이 변수들로 수를 정렬해주기 위해 Comparable 인터페이스를 상속받고, compareTo 메서드를 오버라이딩했다.

 

list에 다 넣었다면, Collections.sort로 list를 정렬해준다. (이 때, NumInfo에서 오버라이딩한 compareTo 메서드가 사용된다.)

이제 list를 사용해 A 배열에 값을 넣어주면 된다!

 

코드

package boj;

// 이차원 배열과 연산 (https://www.acmicpc.net/problem/17140 )

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

public class BOJ_17140 {
	
	private static int[][] A = new int[101][101];
	private static ArrayList<NumInfo> list = new ArrayList<>();
	private static int rSize = 101, cSize = 101;
	private static int[] numCount = new int[101];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// input
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		rSize = 3; cSize = 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());
			}
		}
		
		// solve
		int time = 0;
		while (true) {
			if (A[r - 1][c - 1] == k) break; // A[r - 1][c - 1]가 k가 되면 멈춤
			if (time == 101) break;

			// 행의 개수 >= 열의 개수인 경우, R 연산
			if (rSize >= cSize) R();
			else C(); // 행의 개수 < 열의 개수인 경우, C 연산
			
			time++;
		}
		
		bw.write(((time == 101) ? -1 : time) + "\n"); // time 출력

		bw.flush();
		bw.close();
	}
	
	// 모든 행에 대해서 정렬 수행
	private static void R() throws IOException {
		int newColSize = 0;
		
		for (int i = 0; i < rSize; i++) {
			for (int j = 0; j < cSize; j++) {
				numCount[A[i][j]]++;
				A[i][j] = 0; // 해당 위치의 숫자의 개수를 세어줬으면, A[i][j]를 0으로 바꿔줘야 한다.
			}
			
			for (int idx = 1; idx < numCount.length; idx++) {
				if (numCount[idx] != 0) {
					list.add(new NumInfo(idx, numCount[idx]));
				}
			}
			
			Collections.sort(list); // 정렬
			
			int idx = 0; // i행의 새로운 열의 개수를 저장한다.
			for (NumInfo num : list) {
				A[i][idx++] = num.number;
				A[i][idx++] = num.count;
			}
			
			newColSize = Math.max(newColSize, idx);
			
			list.clear();
			Arrays.fill(numCount, 0);
		}
		
		cSize = newColSize;
	}
	
	// 모든 열에 대해서 정렬 수행
	private static void C() {
		int newRowSize = 0;
		
		for (int j = 0; j < cSize; j++) {
			for (int i = 0; i < rSize; i++) {
				numCount[A[i][j]]++;
				A[i][j] = 0;
			}
			
			for (int idx = 1; idx < numCount.length; idx++) {
				if (numCount[idx] != 0) {
					list.add(new NumInfo(idx, numCount[idx]));
				}
			}
			
			Collections.sort(list); // 정렬
			
			int idx = 0; // j열의 새로운 행의 개수를 저장한다.
			for (NumInfo num : list) {
				A[idx++][j] = num.number;
				A[idx++][j] = num.count;
			}
			
			newRowSize = Math.max(newRowSize, idx);
			
			list.clear();
			Arrays.fill(numCount, 0);
		}
		
		rSize = newRowSize;
	}

	private static class NumInfo implements Comparable<NumInfo> {
		private int number;
		private int count;
		
		NumInfo(int number, int count) {
			this.number = number;
			this.count = count;
		}
		
		@Override
		public int compareTo(NumInfo o) {
			if (this.count == o.count)
				return this.number - o.number;
			return this.count - o.count;
		}
		
	}

}