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

문제

---

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

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

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

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

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

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

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

 

 

 

 

 

풀이

---

문제에서 제시한 대로 구현을 하였다.

 

숫자의 개수를 세는건 배열을 활용하였다. 100까지의 수만 나오기 때문에 101개의 배열을 선언하고 해당 수에 ++ 연산을 해줬다.

int[] number = new int[101];
number[A[i][j]]++;

if(number[A[i][j]] == 1) {
	list.add(A[i][j]);
}

그리고 그때의 값이 1 이 되면 해당 수가 들어있다는 것이기 때문에 list 에 넣어줘 나중에 찾기 편하게 구현하였다.

 

이렇게 수와 개수를 세고 나면

static class number implements Comparable<number>{
	int num, cnt;
	
	number(int num, int cnt){
		this.num = num;
		this.cnt = cnt;
	}

	@Override
	public int compareTo(number n) {
		if(this.cnt == n.cnt) {
			return this.num - n.num;
		}
		return this.cnt - n.cnt;
	}
}

number 클래스를 이용해 해당 수의 개수와 수를 기준으로 오름차순 정렬을 하기위해 선언하였다.

 

이렇게 정렬을 하고 해당 열이나 행에 넣어준다.

 

이 때, 가장 긴 행 또는 열을 계속 체크해서 초기화 시켜줘야한다.

(정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다.)

위의 조건 때문이다.

 

이렇게 정렬 된 것중 원래 배열의 크기보다 작아진 것들은 수를 0으로 초기화 시켜준다.

for(int i = 0 ; i < maxC; i++) {
	for(int j = sizeList.get(i) ; j < maxR ; j++) {
		A[j][i] = 0;
	}
}

sizeList 는 각각 행 이나 열의 크기를 저장하는 리스트다.

 

이렇게 구현하고, 해당 계산에서의 최대값을 최신화 시켜주면된다.

 

<전체코드>

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] A;
	static int r, c, k;
	static int maxR, maxC;
	
	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	public static void main(String[] args) throws IOException{	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		r = parseInt(st.nextToken()) - 1;
		c = parseInt(st.nextToken()) - 1;
		k = parseInt(st.nextToken());
		
		A = new int[100][100];
		
		for(int i = 0 ; i < 3 ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < 3 ; j++) {
				A[i][j] = parseInt(st.nextToken());
			}
		}
		
		maxR = 3;
		maxC = 3;
		
		int time = 0;
		while(time <= 100 && A[r][c] != k) {
			if(maxR >= maxC) {
				calculatorR();
			}
			else {
				calculatorC();
			}
			time++;
		}
		
		if(time > 100) {
			time = -1;
		}
		
		bw.write(time + "\n");
		bw.flush();
		bw.close();
		br.close();
	}
	
	static void calculatorR() {
		
		int max = 0;
		List<Integer> sizeList = new ArrayList<>();
		for(int i = 0 ; i < maxR ; i++) {
			int[] number = new int[101];
			List<Integer> list = new ArrayList<>();
			List<number> numberList = new ArrayList<>();
			for(int j = 0 ; j < maxC; j++) {
				if(A[i][j] == 0) {continue;}
				
				number[A[i][j]]++;
				if(number[A[i][j]] == 1) {
					list.add(A[i][j]);
				}
			}
			
			for(int num : list) {
				numberList.add(new number(num, number[num]));
			}
			
			Collections.sort(numberList);
			
			max = Math.max(max, numberList.size() * 2);
			sizeList.add(numberList.size() * 2);
			
			for(int j = 0 ; j < numberList.size(); j++) {
				A[i][j * 2] = numberList.get(j).num;
				A[i][j * 2 + 1] = numberList.get(j).cnt;
			}
		}	
		
		for(int i = 0 ; i < maxR ; i++) {
			for(int j = sizeList.get(i) ; j < maxC; j++) {
				A[i][j] = 0;
			}
		}		

		if(maxC != max) {
			maxC = max;
		}
	}
	
	static void calculatorC() {
		
		int max = 0;
		List<Integer> sizeList = new ArrayList<>();
		for(int i = 0 ; i < maxC ; i++) {
			int[] number = new int[101];
			List<Integer> list = new ArrayList<>();
			List<number> numberList = new ArrayList<>();
			for(int j = 0 ; j < maxR; j++) {
				if(A[j][i] == 0) {continue;}
				
				number[A[j][i]]++;
				if(number[A[j][i]] == 1) {
					list.add(A[j][i]);
				}
			}
			
			for(int num : list) {
				numberList.add(new number(num, number[num]));
			}
			
			Collections.sort(numberList);
			
			max = Math.max(max, numberList.size() * 2);
			sizeList.add(numberList.size() * 2);
			
			for(int j = 0 ; j < numberList.size(); j++) {
				A[j * 2][i] = numberList.get(j).num;
				A[j * 2 + 1][i] = numberList.get(j).cnt;
			}
		}
		
		for(int i = 0 ; i < maxC; i++) {
			for(int j = sizeList.get(i) ; j < maxR ; j++) {
				A[j][i] = 0;
			}
		}

		if(max != maxR) {
			maxR = max;
		}
	}
	
	static class number implements Comparable<number>{
		int num, cnt;
		
		number(int num, int cnt){
			this.num = num;
			this.cnt = cnt;
		}
	
		@Override
		public int compareTo(number n) {
			if(this.cnt == n.cnt) {
				return this.num - n.num;
			}
			return this.cnt - n.cnt;
		}
	}
}