[백준 / BOJ] 17140번 : 이차원 배열과 연산 - JAVA

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

17140번: 이차원 배열과 연산

R연산과 C연산

R연산과 C연산 중 어떤 것을 진행해야 할지 선택하기 위해 while문 안에서 매번 R과 C를 비교하도록 했다.

 

매 연산마다 R과 C 값이 달라지는데, R연산을 할 때는 C 값이, C연산을 할 때에는 R값이 달라진다. 따라서 R연산을 시작할 때 C를 0으로 초기화하고 map을 채우면서 가장 긴 열을 C에 넣어주었다. 반대로 C연산을 할 때에는 R을 0으로 초기화하고 가장 긴 행의 길이를 R에 넣어주도록 했다.

 

Arrays.sort 와 PriorityQueue

각 행, 혹은 각 열에 존재하는 숫자의 개수를 세고, 다시 해당하는 줄에 넣어줄 때는 정렬이 필요하다. 조건이 "빈도수가 낮은 순서대로, 빈도수가 같다면 숫자가 작은 순서대로"이기 때문에 중간에 정렬해줄 수는 없다.

 

처음에는 Node[] cnt 배열을 만들어서 Arrays.sort(cnt)를 해주었는데, 이 때에는 192ms가 나왔다. 그런데 이 방법은 매번 cnt 배열을 초기화해주어야 하기 때문에 비효율적이라 생각해 PriorityQueue 방법으로 바꿔봤다. cnt를 int 배열로 바꾸고, 한 줄의 숫자를 다 세고 나면 PriorityQueue<Node>에 넣어주도록 변경하자 116ms가 나왔다.

 

확인해보니, Arrays.sort는 O(NlogN)의 시간이 걸리고, PriorityQueue는 O(logN)의 시간이 걸린다고 한다. PriorityQueue가 원소를 넣을 때마다 정렬을 해준다고 생각했는데, 그런 방식으로 작동하는 게 아니고 Heap을 사용해 매번 우선순위가 가장 높은 원소를 출력하는 것이다. 이 때문에 결국 같은 정렬이어도 Arrays.sort보다 PriorityQueue가 확실히 빠르게 연산을 수행하는 것을 확인할 수 있었다.

 

전체 코드

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

// 시간 : 116ms
// 메모리 : 15184KB
public class Main {

	static class Node implements Comparable<Node> {
		int number;
		int cnt;
		
		public Node(int number, int cnt) {
			this.number = number;
			this.cnt = cnt;
		}
		
		@Override
		public int compareTo(Node o) {
			int n = this.cnt - o.cnt;
			if(n != 0) return n;
			else return this.number - o.number;
		}

	}
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int r = Integer.parseInt(st.nextToken()) - 1;
		int c = Integer.parseInt(st.nextToken()) - 1;
		int k = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[100][100];
		
		int R = 3;
		int C = 3;
		for (int i = 0; i < 3; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int time = 0;
		int[] cnt = new int[101];
		PriorityQueue<Node> que = new PriorityQueue<>();
		while(time <= 100) {
			if(map[r][c] == k) break;
			
			if(R >= C) {
				C = 0;
				for (int i = 0; i < R; i++) {
					cnt = new int[101];
					for (int j = 0; j < 100; j++) {
						if(map[i][j] == 0) continue;
						cnt[map[i][j]]++;
						map[i][j] = 0;
					}
					for (int j = 0; j < 101; j++) {
						if(cnt[j] == 0) continue;
						que.offer(new Node(j, cnt[j]));
					}
					int o = 0;
					while(o < 100 && !que.isEmpty()) {
						Node cur = que.poll();
						map[i][o++] = cur.number;
						if(o >= 100) break;
						map[i][o++] = cur.cnt;
					}
                    while(!que.isEmpty()) que.poll();
					if(C < o) C = o;
				}
			} else {
				R = 0;
				for (int j = 0; j < C; j++) {
					cnt = new int[101];
					for (int i = 0; i < 100; i++) {
						if(map[i][j] == 0) continue;
						cnt[map[i][j]]++;
						map[i][j] = 0;
					}
					for (int i = 0; i < 101; i++) {
						if(cnt[i] == 0) continue;
						que.offer(new Node(i, cnt[i]));
					}
					int o = 0;
					while(o < 100 && !que.isEmpty()) {
						Node cur = que.poll();
						map[o++][j] = cur.number;
						if(o >= 100) break;
						map[o++][j] = cur.cnt;
					}
					while(!que.isEmpty()) que.poll();
					if(R < o) R = o;
				}
			}
			time++;
		}
		if(time > 100) System.out.println(-1);
		else System.out.println(time);
		
	}

}