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

문제 >

크기가 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) A[r][c]의 값이 k인지 확인한다. 과정의 반복횟수를 출력한다.

 

2) 행과 열의 크기를 비교한다(초기값은 row = 3, col = 3)

 

3) 행이 열보다 크거나 같은면 R 연산

   a) 각 원소의 값과 그 원소의 값과 같은 원소의 개수를 멤버로 가지는 클래스로 이루어진 ArrayList를 생성한다.

   b) 배열을 행 단위로 읽는다.

   c) 행의 각 열에 있는 값이 ArrayList에 존재한다면, 해당 객체의 원소의 개수를 1증가 시킨다.(만약 값이 0이라면 다음 열로 넘어간다)

   d) c)를 만족하지 않는다면 즉, ArrayList에 존재하지 않는다면, ArrayList에 추가한다.

   e) ArrayList를 원소의 개수, 원소의 값 순서로 오름차순 정렬한다.

   f) ArrayList의 0번째 객체부터 값, 개수를 해당 행의 배열에 담는다.

 

4) 3)을 만족하지 않는다면 C 연산

   a) 각 원소의 값과 그 원소의 값과 같은 원소의 개수를 멤버로 가지는 클래스로 이루어진 ArrayList를 생성한다.

   b) 배열을 열 단위로 읽는다.

   c) 열의 각 행에 있는 값이 ArrayList에 존재한다면, 해당 객체의 원소의 개수를 1증가 시킨다.(만약 값이 0이라면 다음 행로 넘어간다)

   d) c)를 만족하지 않는다면 즉, ArrayList에 존재하지 않는다면, ArrayList에 추가한다.

   e) ArrayList를 원소의 개수, 원소의 값 순서로 오름차순 정렬한다.

   f) ArrayList의 0번째 객체부터 값, 개수를 해당 열의 배열에 담는다.

 

5) 1)로 돌아간다.

 

[JAVA]

package baekjoon;

import java.util.*;

public class BOJ_17140 {
	static int row;
	static int col;
	
	public static class Node implements Comparable<Node>{
		int num;
		int cnt;
		
		Node(int num, int cnt){
			this.num = num;
			this.cnt = cnt;
		}
		
		@Override
		public int compareTo(Node n) {
			if(this.cnt == n.cnt) {
				if(this.num > n.num) return 1;
				else return -1;
			}
			else if(this.cnt > n.cnt) return 1;
			else return -1;
		}
	}
	
	public static int[][] R_op(int[][] a) {
		int[][] b = new int[100][100];
		int max = 0;
		for(int i = 0; i < row; i++) {
			ArrayList <Node> l = new ArrayList<>();
			for(int j = 0; j < col; j++) {
				int num = a[i][j];
				if(num == 0) continue;
				int flag = 0;
				for(int k = 0; k < l.size(); k++) {
					if(l.get(k).num == num) {
						flag = 1;
						l.get(k).cnt++;
						break;
					}
				}
				if(flag == 0) l.add(new Node(num, 1));
			}
			Collections.sort(l);
			int cnt = 0;
			for(int j = 0; j < l.size(); j++) {
				if(cnt > 99) break;
				b[i][cnt++] = l.get(j).num;
				b[i][cnt++] = l.get(j).cnt;
			}
			max = Math.max(max, 2 * l.size());
		}
		col = max;
		return b;
	}
	
	public static int[][] C_op(int[][] a) {
		int[][] b = new int[100][100];
		int max = 0;
		
		for(int i = 0; i < col; i++) {
			ArrayList <Node> l = new ArrayList<>();
			for(int j = 0; j < row; j++) {
				int num = a[j][i];
				if(num == 0) continue;
				int flag = 0;
				for(int k = 0; k < l.size(); k++) {
					if(l.get(k).num == num) {
						flag = 1;
						l.get(k).cnt++;
						break;
					}
				}
				if(flag == 0) l.add(new Node(num, 1));
			}
			Collections.sort(l);
			int cnt = 0;
			for(int j = 0; j < l.size(); j++) {
				if(cnt > 99) break;
				b[cnt++][i] = l.get(j).num;
				b[cnt++][i] = l.get(j).cnt;
			}
			max = Math.max(max, 2 * l.size());
		}
		row = max;
		return b;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt() - 1;
		int c = sc.nextInt() - 1;
		int k = sc.nextInt();
		int[][] a = new int[100][100];
		int result = -1;
		row = 3;
		col = 3;
		
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		
		for(int i = 0; i < 100; i++) {
			if(a[r][c] == k) {
				result = i;
				break;
			}
			if(row >= col) a = R_op(a);
			else a = C_op(a);
		}
		System.out.println(result);
	}
}