Live Today
[코드트리] 격자 숫자 놀이 (Java) 본문
반응형
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
💡 정렬 + 구현 !
✔️ 문제 리뷰
- 소요시간 : 1시간
- 정렬을 위해서 PriorityQueue를 사용하고 매 번 연산을 수행할 때마다 행의 사이즈와 열의 사이즈를 갱신해주면 된다!
✔️ 문제 풀이
- 행의 개수 >= 열의 개수인 경우, 모든 열에 대하여 정렬을 수행한다.
- 행의 개수 < 열의 개수인 경우, 모든 행에 대하여 정렬을 수행한다.
- 목표 숫자에 도달하는 것이 불가능하거나 답이 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;
}
}
'알고리즘 > 코드트리' 카테고리의 다른 글
[코드트리] 이상한 다트 게임 (Java) (0) | 2023.07.01 |
---|---|
[코드트리] 생명과학부 랩 인턴 (Java) (0) | 2023.06.27 |
[코드트리] 시공의 돌풍 (Java) (0) | 2023.06.27 |
[코드트리] 바이러스 백신 (Java) (0) | 2023.06.25 |
[코드트리] 포탑 부수기 (Java) (0) | 2023.06.20 |