[BaekJoon] 17140 이차원 배열과 연산 (Java)

1.  문제 링크

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

2.  문제

요약

• 크기가 3 x 3인 배열 A가 있고 인덱스는 1부터 시작합니다.
• 1초가 지날 때마다 배열에 연산이 적용됩니다.
  1. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행합니다. 행의 개수 ≥ 열의 개수인 경우에 적용됩니다.
  2. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행합니다. 행의 개수 < 열의 개수인 경우에 적용됩니다.
• 한 행 또는 열에 있는 수를 정렬할 때, 각각의 수의 등장 횟수가 커지는 순으로, 그러한 것이 려러가지면 수가 커지는 순으로 정렬합니다.
• 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 하는데, 정렬된 결과를 배열에 넣을 때는 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저입니다.
• 정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있는데, R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변합니다.
• 행 또는 열의 크기가 커진 곳에는 0이 채워지고, 수를 정렬할 때 0은 무시합니다.
• 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버립니다.
• 배열 A에 들어있는 수와 r, c, k가 주어질 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 r, c, k가 주어지고 두 번째 줄부터 3개의 줄에는 100보다 작거나 같은 자연수인 배열 A에 들어있는 수가 주어집니다.
• 출력: 첫 번째 줄에 A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력합니다. 100초가 지나도 A[r][c]가 k가 되지 않으면 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static int r, c, k;
	static int[][] arr;
	static HashMap<Integer, Integer>[] map;
	static void input() {
		Reader scanner = new Reader();
		r = scanner.nextInt() - 1;
		c = scanner.nextInt() - 1;
		k = scanner.nextInt();
		arr = new int[3][3];
		for(int row = 0; row < 3; row++) {
			for(int col = 0; col < 3; col++) arr[row][col] = scanner.nextInt();
		}
	}
	
	static void solution() {
		for(int time = 0; time <= 100; time++) {
			if(arr.length > r && arr[0].length > c) {
				if(arr[r][c] == k) {
					System.out.println(time);
					return;
				}
			}
			if(time == 100) break;
			if(arr.length >= arr[0].length) operationR();
			else operationC();
		}
		System.out.println(-1);
	}
	
	static void operationR() {
		int size = countNumOfRow();
		if(size * 2 > 100) size = 50;
		int[][] temp = new int[arr.length][size * 2];
		for(int len = 0; len < map.length; len++) {
			List<Map.Entry<Integer, Integer>> entryList = new LinkedList<>(map[len].entrySet());
			entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() {
				public int compare(Map.Entry<Integer, Integer> m1, Map.Entry<Integer, Integer> m2) {
					if(m1.getValue() != m2.getValue()) return m1.getValue() - m2.getValue();
					return m1.getKey() - m2.getKey();
				}
			});
			int index = 0;
			for(Map.Entry<Integer, Integer> entry : entryList) {
				temp[len][index] = entry.getKey();
				temp[len][index + 1] = entry.getValue();
				index += 2;
			}
		}
		arr = temp;
	}
	
	static void operationC() {
		int size = countNumOfColumn();
		if(size * 2 > 100) size = 50;
		int[][] temp = new int[size * 2][arr[0].length];
		for(int len = 0; len < map.length; len++) {
			List<Map.Entry<Integer, Integer>> entryList = new LinkedList<>(map[len].entrySet());
			entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() {
				public int compare(Map.Entry<Integer, Integer> m1, Map.Entry<Integer, Integer> m2) {
					if(m1.getValue() != m2.getValue()) return m1.getValue() - m2.getValue();
					return m1.getKey() - m2.getKey();
				}
			});
			int index = 0;
			for(Map.Entry<Integer, Integer> entry : entryList) {
				temp[index][len] = entry.getKey();
				temp[index + 1][len] = entry.getValue();
				index += 2;
			}
		}
		arr = temp;
	}
	
	static int countNumOfRow() {
		map = new HashMap[arr.length];
		int maxSize = Integer.MIN_VALUE;
		for(int row = 0; row < arr.length; row++) {
			map[row] = new HashMap<>();
			for(int col = 0; col < arr[row].length; col++) {
				if(arr[row][col] == 0) continue;
				map[row].put(arr[row][col], map[row].getOrDefault(arr[row][col], 0) + 1);
			}
			maxSize = Math.max(maxSize, map[row].size());
		}
		return maxSize;
	}
	
	static int countNumOfColumn() {
		map = new HashMap[arr[0].length];
		int maxSize = Integer.MIN_VALUE;
		for(int col = 0; col < arr[0].length; col++) {
			map[col] = new HashMap<>();
			for(int row = 0; row < arr.length; row++) {
				if(arr[row][col] == 0) continue;
				map[col].put(arr[row][col], map[col].getOrDefault(arr[row][col], 0) + 1);
			}
			maxSize = Math.max(maxSize, map[col].size());
		}
		return maxSize;
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}