이차원배열과연산 - 17140번(JAVA)

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을 출력한다.

 

package Samsung;

import java.util.*;
import java.io.*;
public class 이차원배열과연산 { //1시간 9분
	
	static int r,c,k;
	static int[][]arr;
	
	
	public static void print() {
		
		for(int i=0; i<arr.length; i++) {
			
			for(int j=0; j<arr[0].length; j++) {
				
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
			
		}
		
		System.out.println();
	}
	
	static class Pair implements Comparable<Pair>{
		
		int num; //숫자
		int cnt; //개수
		
		Pair(int num, int cnt){
			this.num = num;
			this.cnt = cnt;
					
		}
		
		public int compareTo(Pair o) { 
			
			if(this.cnt == o.cnt) {
				
				return this.num-o.num; //갯수가 같으면 숫자 오름차순
				
			}
			
			return this.cnt - o.cnt; //갯수 오름차순
			
		}
		
		
	}
	
	public static void make(ArrayList<int[]>a,int n, int m, boolean tg) { //새로운 이차원배열로 만들어줌
		
		
		int[][] tmp =new int[n][m]; //새로운 값을 담을 이차원배열 선언
		
		if(!tg) { //행단위 정렬 했을때
		
		for(int i=0; i<a.size(); i++) { 
			
			int[] t = a.get(i); 
			
			for(int p=0; p<Math.min(t.length,tmp[0].length); p++) {  //새로운 배열의 크기와 갯수중에 작은 것을 범위의 끝으로 둔다
				tmp[i][p] =t[p]; //i행에 대해서 덮어씌운다.
			}
			
			
		}
		}
		else { //열단위 정렬했을 때
			
			for(int j=0; j<a.size(); j++) {
				
				int[] t = a.get(j);
				
				for(int p=0; p<Math.min(t.length,tmp.length); p++) { //새로운 배열의 크기와 갯수중에 작은 것을 범위의 끝으로 둔다
					tmp[p][j] =t[p]; //j열에 대해서 덮어 씌운다.
				}
				
				
			}
			
		}
		
		arr = tmp;
		
	}
	
	public static void rowsort() { //행정렬
		
		
	
		ArrayList<int[]>res = new ArrayList<>();
		int maxn = arr.length;
		int maxm =0;
		for(int i=0; i<arr.length; i++) {
			/*틀렸던 부분: alist와 list 선언은 꼭 for 문안에서해야한다*/
			int[]nums = new int[101];
			ArrayList<Pair>alist = new ArrayList<>();
			int[]list = arr[i];
			for(int t=0; t<list.length; t++) {
				
				nums[list[t]]++;
			}
			
			for(int p=1; p<101;p++) {
				
				if(nums[p]>0) {
					
					alist.add(new Pair(p,nums[p]));
					
				}
				
			}
			
			Collections.sort(alist);
			int[]tmp = new int[alist.size()*2];
			int idx =0;
			for(Pair p : alist) {
				
				tmp[idx]=p.num;
				idx++;
				tmp[idx]=p.cnt;
				idx++;
				
			}
			
			int sz = tmp.length;
			maxm = Math.max(maxm, sz);
			
			res.add(tmp);
		}
		
		make(res,maxn,Math.min(100, maxm),false);
		
	}
	public static void csort() { //열정렬
		
		
		//ArrayList<Pair>alist = new ArrayList<>();
		ArrayList<int[]>res = new ArrayList<>(); 
		
		int maxn =0;
		int maxm =arr[0].length;
		
		int pn = arr.length;
		
	for(int j=0; j<maxm; j++) {
		int[]nums = new int[101];
		
		/*틀렸던 부분: alist와 list 선언은 꼭 for 문안에서해야한다*/
			ArrayList<Pair>alist = new ArrayList<>(); //숫자와 갯수 쌍을 저장하는 배열리스트
			int[]list = new int[pn];
			
			for(int i=0; i<pn; i++) {
				list[i]=arr[i][j]; //j 열의 값을 가져온다
			}
			
			for(int t=0; t<list.length; t++) {
				
				nums[list[t]]++; //숫자 의 갯수를 증가시켜준다.
			}
			
			for(int p=1; p<101;p++) {
				
				if(nums[p]>0) { //갯수가 하나라도 있는 숫자라면 
					
					alist.add(new Pair(p,nums[p])); //alist에 넣어준다
					
				}
				
			}
			
			Collections.sort(alist); //정렬을 한다.
			int[]tmp = new int[alist.size()*2]; //정렬한 후의 값을 담기 위한 tmp배열
			int idx =0;
			for(Pair p : alist) {
				
				tmp[idx]=p.num;
				idx++;
				tmp[idx]=p.cnt;
				idx++;
				
			}
			
			int sz = tmp.length;
			maxn = Math.max(maxn, sz);
			
			res.add(tmp);
		}
		
		make(res,Math.min(100,maxn),maxm,true); //일차원 배열들의 모음과
		
		
	}
	
	
	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());
		c = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		arr = new int[3][3];
		
		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 answer =0;
		--r;
		--c;
		while(true) {
			
			int n = arr.length;
			int m = arr[0].length;
			
			if(r>=0 && r<n && c>=0 && c<m && arr[r][c]==k) { //r,c 가 현재 arr 범위안에 있다면
				break;
			}
			
			if(answer==100) { //100초가 되면 -1이된다.
				answer=-1;
				break;
			}
			
			if(n>=m) {
				
				rowsort();
				
			}
			else{
				csort();
			}
			
		//	print();
			
			answer++;
			
			
		}
		
		System.out.println(answer);
		
	}

}