[17140] 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

---

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

// 17140 이차원 배열과 연산
public class Main {
	
	static int r, c, k, ROW, COL, TIME;
	static int[][] arr = new int[100][100];
	static int[][] map;
	
	static int[] cnt;
	static ArrayList<Number> row, col;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();
		c = sc.nextInt();
		k = sc.nextInt();
		TIME = 0;
		
		cnt = new int[101];
		
		r--; c--;
		
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		
		ROW = 3; COL = 3;
		
		while(arr[r][c] != k) {			
			map = new int[100][100];
			int maxLen=0;
			
			// R연산
			if(ROW >= COL) {
				for(int i=0; i<ROW; i++) {
					cnt = new int[101];
					row = new ArrayList<Number>();
					
					for(int j=0; j<COL; j++) cnt[arr[i][j]]++;
					
					calcRow();
					Collections.sort(row);
					maxLen = Math.max(row.size(), maxLen);
					
					for(int j=0; j<row.size(); j++) {
						Number n = row.get(j);
						map[i][j*2] = n.num;
						map[i][j*2+1] = n.count;
					}
				}
				COL = maxLen*2;

				copy();
				TIME++;
				if(TIME > 100) {
					System.out.println("-1");
					return;
				}
			// C 연산
			} else {
				for(int i=0; i<COL; i++) {
					cnt = new int[101];
					col = new ArrayList<Number>();
					
					for(int j=0; j<ROW; j++) cnt[arr[j][i]]++;
					
					calcCol();
					Collections.sort(col);
					maxLen = Math.max(col.size(), maxLen);
					
					for(int j=0; j<col.size(); j++) {
						Number n = col.get(j);
						map[j*2][i] = n.num;
						map[j*2+1][i] = n.count;
					}
				}
				ROW = maxLen*2;

				copy();
				TIME++;
				if(TIME > 100) {
					System.out.println("-1");
					return;
				}
			}
//			print();
//			System.out.println();
		}
		
		
		System.out.println(TIME);	
	}
	
	public static void print() {
		for(int i=0; i<100; i++) {
			for(int j=0; j<100; j++) {
				System.out.print(arr[i][j]);
			}
			System.out.println();
		}
	}
	
	public static void copy() {
		for(int i=0; i<100; i++) {
			for(int j=0; j<100; j++) {
				arr[i][j] = map[i][j];
			}
		}
	}
	
	public static void calcRow() {
		
		for(int i=1; i<=100; i++) {
			if(cnt[i] > 0) {
				row.add(new Number(i, cnt[i]));
			}
		}
	}
	
	public static void calcCol() {
		for(int i=1; i<=100; i++) {
			if(cnt[i] > 0) {
				col.add(new Number(i, cnt[i]));
			}
		}
	}
	
}

class Number implements Comparable<Number> {
	int num;
	int count;
	
	Number(int num, int count){
		this.num = num;
		this.count = count;
	}
	
	@Override
	public int compareTo(Number n) {
		if(this.count > n.count) return 1;
		else if(this.count == n.count) {
			if(this.num > n.num) return 1;
		}
		return -1;
	}
	
}

---

행의 수 >= 열의 수 ) R 연산

행의 수 < 열의 수 ) C 연산

간단하게 R, C 연산 두가지를 수행해서 배열 A[r][c] = k 가 오는 최소 시간을 찾는 문제입니다. 저는 cnt 정수 배열을 선언해서 행이나 열에 있는 숫자의 개수를 저장하고, Number 클래스를 선언하여 각각의 연산 수행 시 길이가 달라지기 때문에 ArrayList에 넣어서 숫자의 개수의 오름차순으로 정렬할 수 있게 Comparable을 사용했습니다.

[ 문제 풀이 ]

1. 제일 바깥에 있는 반복문 while 은 arr[r][c] 가 k 이면 빠져나오게 하고, 안에는 크게 R 연산과 C 연산으로 나눕니다.

2. R 과 C 연산 둘다 같은 알고리즘으로 동작하기 때문에 R만 설명해보자면, 행의 개수 >= 열의 개수 일 때 수행 됩니다.

2-1. 숫자의 개수를 저장할 배열 cnt 를 초기화하고, 열마다 R연산을 수행해줄 ArrayList row 도 초기화 해줍니다. 여기서 주어진 숫자(k)는 100을 넘어가지 않기 때문에 cnt 는 101로 길이를 잡아주었습니다.

2-2. 이제 열 별로 있는 숫자를 cnt 에 각각 카운트 해주고 calcRow() 함수를 수행합니다.

2-3. calcRow() 함수는 cnt 배열에 있는 숫자를 ArrayList row 에 저장해주는 함수입니다.

2-4. 그리고 저장된 개수를 오름차순으로 정렬하기 위해서 Collections.sort(row)를 수행합니다.

2-5. maxLen을 구하는 이유는 다음 연산을 할 때의 열의 길이를 정해주기 위해서 입니다.

2-6. 이제 row에 들어있는 숫자를 배열에 넣습니다.

2-7. 다 실행 했으면 바뀐 배열을 원래 arr 배열에 copy() 해주고 정답을 출력할 변수 TIME을 1증가시켜줍니다. 여기서 만약에 TIME이 100이 넘으면 문제에서 -1을 출력하라고 했으므로 -1을 출력하고 return 해줍니다.

3. while 에서 arr[r][c] == k 되면 반복문을 빠져나오는데 그 때 시간인 TIME 을 출력해주면 정답입니다.