Live Today

[코드트리] 격자 숫자 놀이 (Java) 본문

알고리즘/코드트리

[코드트리] 격자 숫자 놀이 (Java)

ilivetoday 2023. 6. 26. 21:49
반응형

https://www.codetree.ai/training-field/frequent-problems/problems/matrix-number-play/description?page=2&pageSize=20 

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

 

💡 정렬 + 구현 !

 

 

✔️ 문제 리뷰

  • 소요시간 : 1시간
  • 정렬을 위해서 PriorityQueue를 사용하고 매 번 연산을 수행할 때마다 행의 사이즈와 열의 사이즈를 갱신해주면 된다!

 

 

✔️ 문제 풀이

  1. 행의 개수 >= 열의 개수인 경우, 모든 열에 대하여 정렬을 수행한다.
  2. 행의 개수 < 열의 개수인 경우, 모든 행에 대하여 정렬을 수행한다.
  3. 목표 숫자에 도달하는 것이 불가능하거나 답이 100초를 초과한다면 -1을 출력한다.

 

 

✅ 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static int R,C,K,result;
	static int rowSize,colSize;
	static int[][] board;
	static class Point implements Comparable<Point>{
		int num,cnt;
		public Point(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		@Override
		public int compareTo(Point o) {
			// 출현하는 횟수가 같은 숫자가 있는 경우에는 해당 숫자가 작은 순서대로 정렬
			if(this.cnt == o.cnt) return this.num - o.num;
			// 정렬 기준은 출현 빈도 수가 적은 순서대로 정렬
			return this.cnt - o.cnt;
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		rowSize = 3;
		colSize = 3;
		
		board = new int[100][100];
		for(int i=0;i<3;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<3;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		} // input end
		
		solve();
		
		// 목표 숫자에 도달하는 것이 불가능하거나 답이 100초를 초과한다면 -1을 출력합니다.
		System.out.println(result > 100 ? -1 : result);
	}

	private static void solve() {
		
		while(board[R-1][C-1] != K) {
			// 목표 숫자에 도달하는 것이 불가능하거나 답이 100초를 초과한다면 -1을 출력합니다.
			if(result == 101) break;
			
			if(rowSize >= colSize) calc_row();
			else calc_col();

			result++;
		}
	}

	private static void calc_col() {
		// 행의 개수가 열의 개수보다 작은 경우
		
		PriorityQueue<Point> pq = new PriorityQueue<>();
		int newRowSize = 0;
		// a. 모든 열에 대하여 정렬을 수행합니다. 정렬 기준은 출현 빈도 수가 적은 순서대로 정렬을 합니다.
		// b. 출현하는 횟수가 같은 숫자가 있는 경우에는 해당 숫자가 작은 순서대로 정렬을 수행합니다.
		// c. 정렬을 수행할 때 숫자와 해당하는 숫자의 출현 빈도 수를 함께 출력해줍니다.
		
		for(int j=0;j<colSize;j++) {
			int[] isChecked = new int[101];
			HashSet<Integer> set = new HashSet<>();
			for(int i=0;i<rowSize;i++) {
				int tempNum = board[i][j];
				if(tempNum == 0) continue;
				set.add(tempNum);
				isChecked[tempNum]++;
				board[i][j] = 0;
			}
			for(int n : set) 
				pq.add(new Point(n, isChecked[n]));
			
			int x = -1;
			while(!pq.isEmpty()) {
				Point p = pq.poll();
				int num = p.num;
				int cnt = p.cnt;
				
				board[++x][j] = num;
				board[++x][j] = cnt;
				if(x == 99) break;
			}
			newRowSize = Math.max(newRowSize, x+1);
		}
		rowSize = newRowSize;
	}

	private static void calc_row() {
		// 행의 개수가 열의 개수보다 크거나 같은 경우
		
		PriorityQueue<Point> pq = new PriorityQueue<>();
		int newColSize = 0;
		// a. 모든 행에 대하여 정렬을 수행합니다. 정렬 기준은 출현 빈도 수가 적은 순서대로 정렬을 합니다.
		// b. 출현하는 횟수가 같은 숫자가 있는 경우에는 해당 숫자가 작은 순서대로 정렬을 수행합니다.
		// c. 정렬을 수행할 때 숫자와 해당하는 숫자의 출현 빈도 수를 함께 출력해줍니다.
		
		for(int i=0;i<rowSize;i++) {
			int[] isChecked = new int[101];
			HashSet<Integer> set = new HashSet<>();
			for(int j=0;j<colSize;j++) {
				int tempNum = board[i][j];
				if(tempNum == 0) continue;
				set.add(tempNum);
				isChecked[tempNum]++;
				board[i][j] = 0;
			}
			for(int n : set) 
				pq.add(new Point(n, isChecked[n]));
			
			int y = -1;
			while(!pq.isEmpty()) {
				Point p = pq.poll();
				int num = p.num;
				int cnt = p.cnt;
				
				board[i][++y] = num;
				board[i][++y] = cnt;
				if(y == 99) break;
			}
			newColSize = Math.max(newColSize, y+1);
		}
		
		colSize = newColSize;
	}
}