백준 17140 - 2차원 배열과 연산

Java

17140 번 - 2차원 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

접근 방법

하드 코딩의 느낌이 강한 문제였다.
총 3가지의 부분으로 나누어 생각하였다.

1. 0초 부터 시작하여 시간 마다 한번씩 R / C 연산을 수행한다. 수행 시간이 100초를 넘어가면 종료하고 -1을 출력한다.
2. R과 C의 크기를 비교한다. R은 행의 크기, C는 열의 크기이며 R >= C이면 R연산, C > R이면 C 연산을 수행한다.
3. R의 연산으로 판단하면 행의 개수 만큼 반복하며 해당하는 행 값마다 숫자 출현 빈도 수를 센다. 그리고 Map의 key, value를 통해 빈도 수를 저장한다. C의 연산도 같다.
4. 3번에서 얻은 Map을 문제 조건에 맞게 정렬한다.
5. 정렬 결과를 각 R연산이면 행, C연산이면 열에 새롭게 갱신한다.
6. 이후 arr[r][c]에 원하는 값이 있는지 확인한다.

구현

각 숫자 출현 빈도 수를 저장하는 방법은 Map을 통하여 구현하였다.
만약 한 행이 [1, 2, 1]이면

1. 1 을 처음 만났으므로 map에 key 1, value 1로 저장
2. 2 를 처음 만났으므로 map에 key 2, value 1로 저장
3. 1 을 또 만났으므로 map의 key 1, value 1을 key 1, value 2로 갱신
   으로 반복하여 빈도 수를 구하였다.
   이후 Collections.sort()와 Comparator를 직접 구현하여 정렬을 하였다.
   자바에서는 Map에 대한 정렬이 없는지, ArrayList<Entry<Integer, Integer>>(map.entrySet())으로 새롭게 ArrayList를 생성하여 정렬할 수 밖에 없었다.

한번 R 혹은 C 연산이 수행 되면 행, 열의 크기가 달라진다.
R 연산이 수행되면 열의 크기가 달라지므로 c를 갱신, C 연산이 수행되면 행의 크기가 달라지므로 r을 갱신하는 방법으로, 다음 초에서 위 r,c를 통해 반복분 조건을 두었다.

또한 연산 결과 후 행이 더 짧아지는 경우 EX) [1,1,1,3,1,1] 이면 [3,1,1,4]로 행이 짧아지므로 뒤에 2개의 수를 0으로 초기화 시켜주는 작업도 해야한다.
이 또한 R연산의 경우 열의 크기 c를 반복문 종료 조건으로 두어, 4개의 갱신 이후 나머지 2개를 0으로 초기화 해주는 작업을 하였다.

코드

import java.util.*;
import java.util.Map.Entry;
import java.io.*;

public class Main {
	static int rr,cc,k , result;
	static int[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	
    	rr = stoi(stk.nextToken()) - 1;		// 뽑아야할 문제
    	cc = stoi(stk.nextToken()) - 1;
    	k = stoi(stk.nextToken());
    	
    	// 테스트 할때만 10, 10 크기임
    	arr = new int[100][100];
    	for(int i = 0; i < 3; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < 3; j++) {
    			arr[i][j] = stoi(stk.nextToken());
    		}
    	}
    	HashMap<Integer, Integer> map = new HashMap<>();
		// Map.Entry 리스트 작성
		List<Entry<Integer, Integer>> list_entries;
		
    	int r = 3, c = 3, time = 0;
    	// 100보다 크면 잘라야함
    	// 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순
    	while(time <= 100) {
    		if(arr[rr][cc] == k) {
    			result = time;
    			break;
    		}
    		//행이 열보다 클때 R 연산
    		if(r >= c) {
    			int biglen = 0;		// 연산 결과 후 최대 길이를 담기 위한 변수
    			for(int i = 0; i < r; i++) {
    				for(int j = 0; j < c; j++) {
    					if(arr[i][j] == 0)	// 0인 값은 연산에서 제외
    						continue;
						// 각 수가 출현하는 빈도를 계산한다.
    					if(!map.containsKey(arr[i][j])){	
    						map.put(arr[i][j], 1);
    					}
    					else {
    						map.replace(arr[i][j], map.get(arr[i][j]) + 1);
    					}
    				}
					// 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다.
    				list_entries = new ArrayList<Entry<Integer, Integer>>(map.entrySet());
    				Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() {
						@Override
						public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
							int diff = o1.getValue().compareTo(o2.getValue());
							if(diff == 0) {
								return o1.getKey().compareTo(o2.getKey());
							}
							return diff;
						}
					});
    				// 새롭게 정렬한 결과를 각 행에 넣어 갱신한다.
    				int idx = 0;
    				for(Entry<Integer, Integer> entry : list_entries) {
    					arr[i][idx++] = entry.getKey();
    					arr[i][idx++] = entry.getValue();
    					if(idx == 100)
    						break;
    				}
    				biglen = Math.max(biglen, idx);
    				// 끝난 이후 0이 아닌 값들은 다 0 처리
    				for(int j = idx; idx < c; idx ++) {
    					if(arr[i][idx] != 0)
    						arr[i][idx] = 0;
    				}
    				map.clear();
    			}
    			// 열의 크기 갱신
    			c = biglen;
    		}
    		//열이 행보다 클때 C 연산
    		else {
    			int biglen = 0;
    			for(int i = 0; i < c; i++) {
    				for(int j = 0; j < r; j++) {
    					if(arr[j][i] == 0)	
    						continue;
						// 각 수가 출현하는 빈도를 계산한다.
    					if(!map.containsKey(arr[j][i])){
    						map.put(arr[j][i], 1);
    					}
    					else {
    						map.replace(arr[j][i], map.get(arr[j][i]) + 1);
    					}
    				}
					// 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다.
    				list_entries = new ArrayList<Entry<Integer, Integer>>(map.entrySet());
    				Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() {
						@Override
						public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
							int diff = o1.getValue().compareTo(o2.getValue());
							if(diff == 0) {
								return o1.getKey().compareTo(o2.getKey());
							}
							return diff;
						}
					});
    				// 새롭게 정렬한 결과를 각 행에 넣어준다
    				int idx = 0;
    				for(Entry<Integer, Integer> entry : list_entries) {
    					arr[idx++][i] = entry.getKey();
    					arr[idx++][i] = entry.getValue();
    					if(idx == 100)
    						break;
    				}
    				biglen = Math.max(biglen, idx);
    				// 끝난 이후 0이 아닌 값들은 다 0 처리
    				for(int j = idx; idx < r; idx ++) {
    					if(arr[idx][i] != 0)
    						arr[idx][i] = 0;
    				}
    				map.clear();
    			}
    			// 행의 크기 갱신
    			r = biglen;
    		}
    		time++;
    	}
    	// 시간이 101초 라는 것은 100초를 초과했다는 것이므로 -1
    	if(time == 101)
    		System.out.println(-1);
    	else
    		System.out.println(result);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐⭐⭐★

후기

끝난 이후 0이 아닌 값들은 다 0 처리하는 과정에서 오류가 생겨, 반례를 하나씩 돌려보며 해결하였다.

개선할 점

없