[백준 / JAVA] 17140. 이차원 배열과 연산 (G4)

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

17140번: 이차원 배열과 연산

 

이 문제의 비밀은 크기가 100이 넘어가는 경우의 처리를 안해도 통과한다는 것이다! 해당 경우를 처리 안하고도 예제가 모두 통과하길래 어인바(Array Index Out of Bound 줄인말 ㅎ)를 띄울 심산으로 제출했는데 통과가 돼버렸다...아무튼 문제 자체는 수의 등장 횟수를 비교한 후 등장 횟수가 같으면 값으로 비교해서 정렬하는 건데 이런 문제는 Comparable를 상속받는 클래스를 만들어서 비교 기준을 직접 정하고, 정렬을 지원하는 자료구조에 넣으면 편하게 구현할 수 있다. 나는 PriorityQueue를 사용했다.

 

100이 넘어가는 경우 처리를 해서 다시 제출했다.(제대로 된지는 몰?루)

 

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

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken()) - 1;
		C = Integer.parseInt(st.nextToken()) - 1;
		K = Integer.parseInt(st.nextToken());
		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());
		}
		while (time < 101) {
			if (map[R][C] == K)
				break;
			time++;
			if (mapR >= mapC)
				calcR();
			else
				calcC();
		}
		if (time == 101)
			System.out.println(-1);
		else
			System.out.println(time);
	}

	static int time = 0, mapR = 3, mapC = 3, R, C, K, map[][] = new int[100][100], dr[] = { -1, 1, 0, 0 },
			dc[] = { 0, 0, -1, 1 };
	static PriorityQueue<Number> pq = new PriorityQueue<>();

	static void print() {
		for (int m[] : map)
			System.out.println(Arrays.toString(m));
	}

	static void calcR() {
		int maxC = 0;
		for (int i = 0; i < mapR; i++) {
			int arr[] = new int[101];
			pq.clear();
			for (int j = 0; j < mapC; j++)
				arr[map[i][j]]++;
			for (int j = 1; j < arr.length; j++)
				if (arr[j] > 0)
					pq.add(new Number(j, arr[j]));
			maxC = Math.max(pq.size() * 2, maxC);
			Arrays.fill(map[i], 0);
			int k = 0;
			while (!pq.isEmpty()) {
				Number n = pq.poll();
				if (k == 100)
					break;
				map[i][k++] = n.value;
				if (k == 100)
					break;
				map[i][k++] = n.count;
			}
		}
		maxC = maxC >= 100 ? 100 : maxC;
		mapC = maxC;
	}

	static void calcC() {
		int maxR = 0;
		for (int i = 0; i < mapC; i++) {
			int arr[] = new int[101];
			pq.clear();
			for (int j = 0; j < mapR; j++)
				arr[map[j][i]]++;
			for (int j = 1; j < arr.length; j++)
				if (arr[j] > 0)
					pq.add(new Number(j, arr[j]));
			maxR = Math.max(pq.size() * 2, maxR);
			for (int j = 0; j < 100; j++)
				map[j][i] = 0;
			int k = 0;
			while (!pq.isEmpty()) {
				Number n = pq.poll();
				if (k == 100)
					break;
				map[k++][i] = n.value;
				if (k == 100)
					break;
				map[k++][i] = n.count;
			}
		}
		maxR = maxR >= 100 ? 100 : maxR;
		mapR = maxR;
	}

	static class Number implements Comparable {
		int value, count;

		public Number(int value, int count) {
			super();
			this.value = value;
			this.count = count;
		}

		@Override
		public int compareTo(Object o) {
			Number number = (Number) o;
			if (this.count == number.count)
				return this.value - number.value;
			return this.count - number.count;
		}
	}
}