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

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

 

 

[ 문제 요약 ]

• 크기가 3*3인 배열이 주어집니다.
• 인덱스는 1부터 시작하며 1초가 지날 때마다 배열에 아래 연산을 조건에 따라 실행합니다. (행 개수 >= 열 개수 인 경우 R 연산, 아닌 경우 C 연산)
• R 연산 : 배열의 모든 행에 대해 정렬 수행(행 개수 >= 열 개수인 경우 적용)
• C 연산 : 배열의 모든 열에 대해 정렬을 수행(행 개수 < 열 개수인 경우 적용)
• 한 행 또는 열에 있는 수 정렬 시 각 수가 몇 번 나왔는지 알아야 합니다.
• 그다음, 수의 등장 횟수 기준 오름차순, 같다면 수기준으로 오름차순으로 정렬합니다.
• 그다음 배열에 정렬된 결과를 다시 넣습니다. 정렬된 결과를 배열에 넣을 때는 수와 등장 횟수를 모두 넣으며 순서는 수가 먼저입니다.
• [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은 무시합니다.
• 행 또는 열 크기가 100을 넘어가면 처음 100개를 제외한 나머지는 버립니다.
• 배열에 들어있는 수와 R, C, K가 주어질 때, A[R][C]의 값이 K가 되기 위한 최소 시간을 구합니다. 100초가 지나도 K가 되지 않으면 -1을 출력합니다.

 

[ 테스트 케이스 설명 ]

1 2 3 // R,C,K가 주어짐(1<=100)
1 2 1 // 3*3크기에 들어있는 수가 주어짐(1<=100)
2 1 3
3 3 3
A[R][C]의 값이 K가 되는 가장 짧은 시간 : 2

 

 

[ 알고리즘 분류 ]

• 구현
• 정렬
• 시뮬레이션

 

[ 문제 해설 ]

 

언제 R을 실행하고, 언제 C를 실행하는지만 알면 일반적인 구현 문제입니다.

 

행중 가장 긴 행 길이와, 열중 가장 긴 열 길이 중, 행길이가 열길이 이상이면 R 실행, 아니면 C 실행입니다.

 

그 후 문제에 맞게 R과 C만 잘 구현해 주면 됩니다.

 

[ 정답 코드 ]

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

class Main{
	
	static final int len = 100;
	static int xLen = 3;
	static int yLen = 3;
	static int R, C, K;
	static int map[][];
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken()) - 1;
		C = Integer.parseInt(st.nextToken()) - 1;
		K = Integer.parseInt(st.nextToken());
		map = new int[len + 1][len + 1];
		
		for(int y=0; y<yLen; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<xLen; x++)
				map[y][x] = Integer.parseInt(st.nextToken());
		}
		
		System.out.print( solve() );
	}
	static int solve() {
		for(int time = 0; time<=len; time++)
		{
			if(map[R][C] == K)
				return time;
			
			if(yLen >= xLen)
				R();
			else
				C();
		}
		
		return -1;
	}
	static void R() {
		for(int y=0; y<yLen; y++)
		{
			int arr[] = order(map[y]);
			xLen = Math.max(xLen, arr.length);
			
			for(int x=0; x<arr.length; x++)map[y][x] = arr[x];
			for(int x=arr.length; x<=len; x++)map[y][x] = 0;
		}
	}
	static void C() {
		for(int x=0; x<xLen; x++)
		{
			int xrr[] = getXrr(x);
			int arr[] = order(xrr);
			yLen = Math.max(yLen, arr.length);
			
			for(int y=0; y<arr.length; y++)map[y][x] = arr[y];
			for(int y=arr.length; y<=len; y++)map[y][x] = 0;
		}
	}
	static int[] getXrr(int x) {
		int xrr[] = new int[yLen];
		
		for(int y = 0; y<xrr.length; y++)
			xrr[y] = map[y][x];
		
		return xrr;
	}
	static int[] order(int arr[]) {
		int counting[] = new int[len + 1];
		
		for(int i=0; i<arr.length; i++)
		{
			if(arr[i] == 0)continue;
			counting[arr[i]]++;
		}
		PriorityQueue<Node> pq = new PriorityQueue<>();
		
		for(int i=1; i<=len; i++)
			if(counting[i] > 0)
				pq.add(new Node(counting[i], i));
		
		int result[] = new int[Math.min(100, pq.size()*2)];
		
		int i = 0;
		
		while(!pq.isEmpty())
		{
			Node now = pq.poll();
			result[i++] = now.num;
			result[i++] = now.cnt;
		}
		
		return result;
	}
	static class Node implements Comparable<Node>{
		int cnt;
		int num;
		Node(int c, int n){
			cnt = c;
			num = n;
		}
		@Override
		public int compareTo(Node o) {
			return cnt != o.cnt ? cnt - o.cnt : num - o.num;
		}
	}
}

 

[ 여러 반례들 ]

2 1 4
1 2 1
2 1 3
3 3 3
=>91

5 4 3
1 3 5
2 4 6
7 8 2
=>-1

10 4 3
1 3 5
2 4 6
7 5 2
=>10

10 14 3
1 3 5
2 4 3
7 5 2
=>-1

5 14 3
1 3 5
2 4 3
1 2 3
=>29

5 10 6
1 3 5
6 2 3
1 2 3
=>45

1 1 6
1 2 3
6 2 3
1 2 3
=>6

3 1 6
1 2 6
6 2 3
4 5 3
=>-1

2 1 6
1 2 6
5 2 3
4 5 3
=>-1

2 5 6
4 2 6
5 8 3
4 5 3
=>-1

2 3 4
4 2 6
5 8 3
4 5 3
=>18

1 2 3
4 5 6
7 8 9
10 11 12
=>6

9 8 3
6 5 4
3 2 1
10 9 8
=>-1

1 1 1
2 2 2
3 3 3
4 4 4
=>4

4 4 2
3 3 3
2 2 2
1 1 1
=>7

1 2 3
3 2 1
4 3 2
5 4 3
=>38

9 8 3
1 2 3
1 2 3
1 2 3
=>17

1 2 3
1 2 3
1 2 3
1 2 3
=>4

4 3 22
5 4 71
93 24 51
1 35 2
=>73

1 1 1
2 2 2
3 5 19
21 43 65
=>8

9 9 9
9 9 9
8 8 8
7 7 7
=>42

1 3 5
2 4 6
3 6 9
4 8 12
=>15

4 3 2
5 4 3
2 7 6
99 88 77
=>6

9 8 2
93 72 64
28 43 26
100 82 31
=>15

1 2 99
98 72 53
82 31 92
100 82 62
=>-1

1 2 98
98 72 53
82 31 92
100 82 62
=>-1

1 2 3
98 72 53
82 31 92
100 82 62
=>22

10 15 1
1 1 1
1 1 1
1 1 1
=>-1

1 15 1
6 1 2
8 2 3
2 10 3
=>17