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

문제

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

17140번: 이차원 배열과 연산

티어

분류

구현

코드

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

public class Main
{
    static int[][] arr = new int[101][101];
    static int yLength = 3;
    static int xLength = 3;
    
    public static class Number implements Comparable<Number> {
        int num;
        int cnt;
        
        Number(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
        
        @Override
        public int compareTo(Number n) {
            if (this.num == 0 || n.num == 0) {
                if (this.num == 0 && n.num == 0) {
                    return 0;
                }
                return this.num == 0 ? 1 : -1;
            } 
            if (this.cnt == n.cnt) return this.num - n.num;
            else return this.cnt - n.cnt;
        }
    }
    
	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());
		for (int i = 0; i < 3; i++) {
		    st = new StringTokenizer(br.readLine(), " ");
		    for (int j = 0; j < 3; j++) {
		        arr[i][j] = Integer.parseInt(st.nextToken());
		    }
		}
		
		int time = 0;
		while (!isEnd(r, c, k)) {
		    if (time > 100) {
		        time = -1;
		        break;
		    }
		    
		    boolean nextCalculationIsColumn = getNextCalculationIsColumn();
		    if (nextCalculationIsColumn) {
		        calculateColumn();
		    }
		    else {
		        calculateRow();
		    }
		    time++;
		}
		System.out.println(time);
	}
	
	public static boolean isEnd(int r, int c, int k) {
	    return arr[r][c] == k;
	}
	
	public static boolean getNextCalculationIsColumn() {
	    if (xLength > yLength) return false;
	    else return true;
	}
	
	public static void calculateColumn() {
	    int[][] arrCopy = new int[101][101];
	    int newXLength = 0;
	    for (int i = 0; i < yLength; i++) {
	        HashMap<Integer, Integer> map = new HashMap<>();
	        for (int j = 0; j < xLength; j++) {
	            if (arr[i][j] == 0) continue;
	            map.put(arr[i][j], map.getOrDefault(arr[i][j], 0) + 1);
	        }
	        
	        ArrayList<Number> newNumber = new ArrayList<>();
	        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
	            newNumber.add(new Number(entry.getKey(), entry.getValue()));
	        }
	        newXLength = Math.max(newXLength, newNumber.size() * 2);
	        Collections.sort(newNumber);
	        
	        for (int j = 0; j < newNumber.size(); j++) {
	            if (j >= 50) break;
	            arrCopy[i][2 * j] = newNumber.get(j).num;
	            arrCopy[i][2 * j + 1] = newNumber.get(j).cnt;
	        }
	    }
	    xLength = Math.min(100, newXLength);
	    arr = arrCopy;
	}
	
	public static void calculateRow() {
	    int[][] arrCopy = new int[101][101];
	    int newYLength = 0;
	    for (int i = 0; i < xLength; i++) {
	        HashMap<Integer, Integer> map = new HashMap<>();
	        for (int j = 0; j < yLength; j++) {
	            if (arr[j][i] == 0) continue;
	            map.put(arr[j][i], map.getOrDefault(arr[j][i], 0) + 1);
	        }
	        
	        ArrayList<Number> newNumber = new ArrayList<>();
	        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
	            newNumber.add(new Number(entry.getKey(), entry.getValue()));
	        }
	        newYLength = Math.max(newYLength, newNumber.size() * 2);
	        Collections.sort(newNumber);
	        for (int j = 0; j < newNumber.size(); j++) {
	            if (j >= 50) break;
	            arrCopy[2 * j][i] = newNumber.get(j).num;
	            arrCopy[2 * j + 1][i] = newNumber.get(j).cnt;
	        }
	    }
	    yLength = Math.min(100, newYLength);
	    arr = arrCopy;
	}
}

코드 설명

정렬과 초기화가 중요한 문제이다.

정렬은 클래스를 구현할 때 compareTo를 구현하여 ArrayList를 정렬했지만 PriorityQueue를 사용하여 바로 정렬을 하는 방법도 있다.

성능은 PriorityQueue가 더 좋을 것이라고 생각한다.

 

초기화가 중요한 이유는 맵의 일부가 바뀌기 때문에 바꾸지 않은 부분은 이전 배열의 결과가 남아있을 수 있기 때문이다.

따라서 arrCopy를 계산 과정마다 두고 복사하는 방법을 취했다.

 

저장은 int의 이중 배열로 저장을 하지만 정렬을 할 때에는 Number라는 클래스를 만들었고 이 클래스에 number와 count를 담는 것으로 하였다.

정렬을 num, cnt 쌍으로 하지 않는다면 뒤죽박죽 섞여 저장될 수 있기 때문에 한 번에 클래스로 묶는 방법을 선택했다.

 

0의 경우 정렬과 계산에 포함하여서는 안되는데, 계산 과정에서 이를 간과했다.

정렬에서는 num이 0, cnt가 0인 부분은 맨 뒤로 정렬하면 되고 계산 과정에서는 아예 신경쓰지 않으면 된다.