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

문제

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

17140번: 이차원 배열과 연산

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main_17140_이차원배열과연산 {

	static int r, c, k;
	static int[][] A;
	static int rSize = 3, cSize = 3;
    public static void main(String[] args) throws IOException {
        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());
        A = new int[101][101];
        for(int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //입력받기 끝
        
        //행의 개수 ≥ 열의 개수 -> R연산
        //행의 개수 < 열의 개수 -> C연산
        int answer = 0;
        while(A[r][c] != k) {
            if(answer > 100) {
                answer = -1;
                break;
            }
            if(rSize >= cSize) {//R연산
                R();
            }
            else {//C연산
                C();
            }
            answer++;
        }
        System.out.println(answer);
    }
    
    static void R() {
    	int tmpSize = 0;
    	for(int i = 0; i < rSize; i++) {
    		PriorityQueue<Data> pq = new PriorityQueue<>();
        	Map<Integer, Integer> map = new HashMap<>(); //숫자, 카운트
    		for(int j = 0; j < cSize; j++) {
    			if(A[i][j] == 0) continue;
    			map.compute(A[i][j], (num, count) -> count == null ? 1: count + 1);
    		}
    		map.forEach((k, v) -> pq.add(new Data(k, v)));
    		int idx = 0;
    		while(!pq.isEmpty()) {
    			Data now = pq.poll();
    			A[i][idx++] = now.number;
    			A[i][idx++] = now.count;
    		}
    		tmpSize = Math.max(tmpSize, idx);
    		while(idx <= 99) {
    			A[i][idx++] = 0; //남은 배열 다 0으로 채우기
    		}
    	}
    	cSize = tmpSize;
    }
    
    static void C() {
    	int tmpSize = 0;
    	for(int j = 0; j < cSize; j++) {
    		PriorityQueue<Data> pq = new PriorityQueue<>();
    		Map<Integer, Integer> map = new HashMap<>(); //숫자, 카운트
    		for(int i = 0; i < rSize; i++) {
    			if(A[i][j] == 0) continue;
    			map.compute(A[i][j], (num, count) -> count == null ? 1: count + 1);
    		}
    		map.forEach((k, v) -> pq.add(new Data(k, v)));
    		int idx = 0;
    		while(!pq.isEmpty()) {
    			Data now = pq.poll();
    			A[idx++][j] = now.number;
    			A[idx++][j] = now.count;
    		}
    		tmpSize = Math.max(tmpSize, idx);
    		while(idx <= 99) {
    			A[idx++][j] = 0; //남은 배열 다 0으로 채우기
    		}
    	}
    	rSize = tmpSize;
    }
}
class Data implements Comparable<Data>{
	int number;
	int count;
	
	public Data(int number, int count) {
		this.number = number;
		this.count = count;
	}

	@Override
	public int compareTo(Data o) {
		if(this.count > o.count) {
			return 1;
		} else if(this.count == o.count) {
			return this.number - o.number; //카운트가 같으면 number가 작은거
		}
		return -1;
	}
	
}

 

접근 방법

 

자료 형

배열의 최대 크기는 100까지이므로 100까지 선언했다.

가로 사이즈와 세로 사이즈는 처음에는 반드시 3으로 시작하기 때문에 3으로 따로 변수를 주었다.

처음에는 배열 대신에 list를 사용하려고 했는데 그렇게 되면 기존에 작성했던 배열보다 짧아지는 경우 남는 값들을 0으로 처리하든지 remove를 해주는 과정이 필요한데 100개의 배열을 0으로 바꿔주는 것이 생각보다 시간이 오래 걸리지 않는다는 것을 알았다.

 

알고리즘

R연산과 C연산은 다루는 인덱스의 차이를 제외하고는 거의 비슷하지만 헷갈리기 때문에 따로 뺐다.

Map<Integer, Integer>로 숫자와 숫자의 개수를 저장해주었는데

Map을 숫자의 개수에 따라서 정렬하는 과정을 거쳐야하기 때문에 PriorityQueue를 사용해주었다.

큐에 넣어줄 데이터를 위해 따로 클래스를 작성하여 number와 count변수를 선언해주고 Comparable<> 인터페이스를 상속받아 compareTo를 작성해주었다.

count가 같다면 숫자가 작은 순으로 정렬

pq에다가 연산을 해야할 행or열을 넣어준 뒤 하나씩 poll하여 배열에 새롭게 다시 넣어주었다.

행/열의 최대 값이 현재 전체 이차원 배열의 크기가 될것이기 때문에 max값을 따로 저장해주었다.

idx를 제외한 뒷부분은 모두 0으로 바꾼다.

모든 연산이 끝나면 rSize / cSize를 업데이트 해준다.