[JAVA] BOJ(백준) - 이차원 배열과 연산 - 17140

문제내용

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

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가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

---

문제풀이

문제힌트가 있는 만큼 문제 이해하는데 크게 어려운게 없고, 문제에서 주어진대로 조건에 따라 R,C연산을 해주면된다.

 

1. 1~n까지 각 숫자가 얼마나 나오는지 체크해준다.

2. 1~n까지 숫자, 등장횟수를 Number 클래스 객체로 list에 넣어준다.

3. 조건에 따라 정렬해준다. -> Compartor 익명함수 or Number클래스에서 Comparble 상속받아서 정렬.

4. 정렬된 값을 임시 배열에 순서대로 넣어주고, 최대사이즈를 구해준다. -> 최대사이즈가 100이 넘어가면 100으로.

5. 기존 배열을 최대사이즈에 맞게 재정의하고, 임시배열의 값을 넣어준다.

 

k의 숫자를 찾을때까지 1~5과정을 반복해주면서 time을 1씩 늘려주면된다.

 

---

풀이

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

public class Main {
	static private int r,c,k;
	static private int[][] map;
	static private class Number implements Comparable<Number>{
		int n;
		int cnt;
		public Number(int n, int cnt) {
			this.n = n;
			this.cnt = cnt;
		}
		
		@Override
		public int compareTo(Number o) {
			if(this.cnt>o.cnt) return 1;
			else if(this.cnt<o.cnt) return -1;
			else {
				if(this.n>o.n) return 1;
				else return -1;
			}
		}
	}
	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());
		map = new int[3][3];
		
		for(int i=0; i<3; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		int time = 0;
		while(true) {
			//100초 보다 더걸리면 종료.
			if(time>100) {
				time = -1;
				break;
			}
			
			//k값 찾으면 종료.
			if(r<map.length && c<map[0].length) {
				if(map[r][c]==k) break;
			}
			
			if(map.length>=map[0].length) operationR();
			else operationC();
			
			time++;
		}
		
		System.out.println(time);
	}
	
	public static void operationR() {
		int size = Integer.MIN_VALUE;//최대 사이즈
		int[][] sub = new int[101][101];//임시 배열
		for(int i=0; i<map.length; i++) {
			int[] numArr = new int[101];
			List<Number> list = new ArrayList<>();
			
			//1. 1~n까지 숫자 카운트.
			for(int j=0; j<map[0].length; j++) {
				if(map[i][j]==0) continue;
				numArr[map[i][j]]++;
			}
			
			//2. 리스트에 숫자 & 등장횟수를 넣기.
			for(int j=1; j<numArr.length; j++) {
				if(numArr[j]==0) continue;
				list.add(new Number(j, numArr[j]));
			}
			
			//3. 정렬
			Collections.sort(list);
			
			//4. 정렬된 값을 임시배열에 넣고, 최대사이즈 구하기
			int k=0;
			for(int j=0; j<list.size(); j++) {
				sub[i][k] = list.get(j).n;
				sub[i][k+1] = list.get(j).cnt;
				k+=2;
			}
			size = Math.max(size, k);
		}
		if(size>100) size=100;
		
		//5. 기존 배열 재정의 및 임시배열의 값 넣기.
		map = new int[map.length][size];
		for(int i=0; i<map.length; i++) {
			for(int j=0; j<size; j++) {
				map[i][j]=sub[i][j];
			}
		}
	}

	//R연산과 동일(인덱스만 바뀜)
	public static void operationC() {
		int size = Integer.MIN_VALUE;
		int[][] sub = new int[101][101];
		for(int j=0; j<map[0].length; j++) {
			int[] numArr = new int[101];
			List<Number> list = new ArrayList<>();
			for(int i=0; i<map.length; i++) {
				if(map[i][j]==0) continue;
				numArr[map[i][j]]++;
			}
			for(int i=1; i<numArr.length; i++) {
				if(numArr[i]==0) continue;
				list.add(new Number(i, numArr[i]));
			}
			Collections.sort(list);
			int k=0;
			for(int i=0; i<list.size(); i++) {
				sub[k][j] = list.get(i).n;
				sub[k+1][j] = list.get(i).cnt;
				k+=2;
			}
			size = Math.max(size, k);
		}
		if(size>100) size=100;
		map = new int[size][map[0].length];
		for(int i=0; i<size; i++) {
			for(int j=0; j<map[0].length; j++) {
				map[i][j]=sub[i][j];
			}
		}
	}
}

---

마치며

처음에 풀었을때 4번과정에서 k를 for(int i=0, k=0; i<list.size(); i++,k+=2) 를 이용해 풀었는데 답이 다르게나온다.. 이부분은 왜 다르게 나오는지 아직 모르겠는데 다시한번 살펴봐야 할듯 하다!