[BOJ] 17140 이차원 배열과 연산 - Java

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

17140번: 이차원 배열과 연산

---

1. 문제 요약

3x3 크기의 배열이 있다. 

1초마다 두 가지 연산 중 하나를 수행한다.

행의 개수 >= 열의 개수 일 경우, R 연산(행 정렬)을 수행하고

행의 개수 < 열의 개수 일 경우, C 연산(열 정렬)을 수행한다.

정렬은 다음과 같이 이루어진다.각 행 또는 열에 수가 등장하는 횟수 오름차순, 등장 횟수가 같다면 수 오름차순으로 정렬한다.배열에 다시 넣어줄 때는 등장하는 수, 등장 횟수 순서로 넣어준다.예를 들어, 1 2 1 일 경우 1이 2번, 2가 1번 등장하므로 2 1 1 2 가 된다.r, c, k가 주어졌을 때, r,c좌표 값이 k가 되는 최소 시간을 출력한다.

 

* 수를 정렬할 때 0은 무시한다.

* 행 또는 열의 크기가 100을 넘어가는 경우 처음 100개를 제외한 나머지는 버린다. => 배열 최대 크기는 100x100 이라는 것을 의미

 

2. 풀이

시뮬레이션으로 풀었다.

 

최대 100초 동안 수행하므로 다음을 100번 반복한다.

1, map[r][c] == k일 경우 반복을 멈춘다.

2. 행 개수 >= 열 개수 이면 R을 수행,

    행 개수 < 열 개수 이면 C를 수행한다.

3. 정렬은

 - 등장횟수 오름차순, 등장횟수 같으면 수 오름차순으로 정렬하기 위해 Priority Queue를 사용하였다. - 1~100까지 수의 등장 횟수를 저장하는 배열을 만들었다.1) 하나의 행 또는 열에서 map의 좌표를 인덱스로 하여 등장 횟수를 저장해준다.    => 등장횟수 저장과 동시에 map의 값은 0으로 초기화 해준다.

2) 등장횟수 배열에서 등장 횟수가 0이 아닐 경우, 인덱스와 값을 pq에 넣어준다.

3) pq가 빌 때까지 하나씩 꺼내서 map 에 수(인덱스), 등장횟수(값) 순서로 넣어준다.

   => 가로 길이 또는 세로 길이의 max를 갱신해준다.

         => 반복문 처음으로 돌아갈 때 R 또는 C 중 어떤 연산을 수행할지 판단하는 기준이기 때문

 

 

3. 코드

import java.util.*;
import java.io.*;

public class BOJ_17140_이차원배열과연산 {

	static int[] numCnt;
	static int[][] map;
	static List<Integer> list;
	static int r,c,k, ans, rLen, cLen;
	
	public static void main(String[] args) throws Exception {
		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());
		rLen = 3;
		cLen = 3;
		map = new int[100][100];
		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());
			}
		} //입력 끝
		
		solution();
		System.out.println(ans);
	}
	
	static void solution() {
		for(int t=0; t<100; t++) {
			if (map[r][c] == k) {
				break;
			}
			//2. 배열 크기 확인 -> R연산할지 C연산할지 체크
			if (rLen >= cLen) doR();
			else doC();
			ans++;
		}
		if (map[r][c] != k) ans = -1;
	}
	
	static void doR() { //행마다 정렬
		for (int r=0; r<rLen; r++) {
			PriorityQueue<Node> pq = new PriorityQueue<> ();
			numCnt = new int[101];
			
			for (int c=0; c<cLen; c++) {
				numCnt[ map[r][c] ]++;
				map[r][c] = 0;
			}
			//1. pq에 넣어줌 -> 자동정렬
			for (int n=1; n<=100; n++) {
				if (numCnt[n] == 0) continue;
				pq.offer(new Node(n, numCnt[n]));
			}
			//2. map에 다시 넣어줌
			int len = 0;
			while(!pq.isEmpty()) {
				Node cur = pq.poll();
				map[r][len++] = cur.num;
				map[r][len++] = cur.cnt;
			}
			cLen= Math.max(cLen, len+1);
		}
	}
	
	static void doC() { //열마다 정렬
		for (int c=0; c<cLen; c++) {
			PriorityQueue<Node> pq = new PriorityQueue<> ();
			numCnt = new int[101];
			
			for (int r=0; r<rLen; r++) {
				numCnt[ map[r][c] ]++;
				map[r][c] = 0;
			}
			//1. pq에 넣어줌 -> 자동정렬
			for (int n=1; n<=100; n++) {
				if (numCnt[n] == 0) continue;
				pq.offer(new Node(n, numCnt[n]));
			}
			//2. map에 다시 넣어줌
			int len = 0;
			while(!pq.isEmpty()) {
				Node cur = pq.poll();
				map[len++][c] = cur.num;
				map[len++][c] = cur.cnt;
			}
			rLen= Math.max(rLen, len+1);
		}
	}
	
	static class Node implements Comparable<Node>{
		int num, cnt;
		Node(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		@Override
		public int compareTo(Node o) {
			if (this.cnt==o.cnt) {
				return this.num-o.num;
			} else {
				return this.cnt-o.cnt;
			}
		}
	}
}