👨💻 문제
✍️ 풀이
🗃️ 정렬
우선 정렬이 필요해보인다.
그렇다면 어떻게 정렬을 해야할까?
- 내림차순으로 정렬
4 4 4 4 4 4 4 4 4 4 4 4 3 2 1
4 4 4 4 4
4 4 4 4 4
4 4 3 2 1이런 경우 어떠한 경우에 4에 4를 올려도 되는지 판단하기가 어려워진다.
- 오름차순으로 정렬
주어진 조건과 반대의 순서로 쌓는다고 생각한다.
현재까지 쌓은 수보다 같거나 높은 수를 쌓을 수 있다.
1 1 1 1 1 2 2 2 3 3 3 4 4 4 4
1 1 2 3 4
1 1 2 3 4
1 2 3 4 4이러면 큰 수를 언제 중복하여 사용해도 되는지 알 수 있다.
현재 주사위를 놓을 수 없다면 일단 미뤄두고 놓을 수 있는 가장 작은 수를 놓는다.
이렇게만 해서 풀어질까 했는데 풀어졌다.
🎱 우선순위 큐
주석을 보는 게 가장 좋은 설명일 것 같다.
while (!pq.isEmpty()) {
int value = pq.poll();
// 쌓을 수 있다면 쌓고
if (currentTowerHeight <= value) {
currentTowerHeight++;
}
// 없다면 미뤄둔다
else {
nextPq.add(value);
}
// 더 쌓을 수 없다면 현재 쌓던 탑을 완성 처리
if (pq.isEmpty()) {
currentTowerHeight = 0;
towersCnt++;
// 아직 안 쌓은 주사위가 있다면 다시 쌓기
if (!nextPq.isEmpty()) {
pq = nextPq;
nextPq = new PriorityQueue<>();
}
}
}📄 전체 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class _15703 {
private static PriorityQueue<Integer> pq = new PriorityQueue<>();
private static PriorityQueue<Integer> nextPq = new PriorityQueue<>();
private static int towersCnt = 0;
private static int currentTowerHeight = 0;
public static void main(String[] args) throws IOException {
input();
while (!pq.isEmpty()) {
int value = pq.poll();
// 쌓을 수 있다면 쌓고
if (currentTowerHeight <= value) {
currentTowerHeight++;
}
// 없다면 미뤄둔다
else {
nextPq.add(value);
}
// 더 쌓을 수 없다면 현재 쌓던 탑을 완성 처리
if (pq.isEmpty()) {
currentTowerHeight = 0;
towersCnt++;
// 아직 안 쌓은 주사위가 있다면 다시 쌓기
if (!nextPq.isEmpty()) {
pq = nextPq;
nextPq = new PriorityQueue<>();
}
}
}
System.out.println(towersCnt);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
pq.add(Integer.parseInt(st.nextToken()));
}
}
}🔍️ 리뷰
다시 보니 좀 개선할 수 있는 사항들이 보인다.
각 주사위들은 입력 시에 우선순위 큐에 들어가며 정렬된다.
그렇기에 nextPq 및 2회차의 pq는 굳이 우선순위 큐로 구현되지 않아도 된다.
그냥 큐 쓰는 게 더 빠르다.
if (pq.isEmpty()) {
currentTowerHeight = 0;
towersCnt++;
// 아직 안 쌓은 주사위가 있다면 다시 쌓기
if (!nextPq.isEmpty()) {
pq = nextPq;
nextPq = new PriorityQueue<>();
}
}그리고 위 반복문이 while문 안에 들어있을 필요는 없어보인다.
애초에 반복 조건이 큐에 요소가 남아있을 때인데, 저걸 항상 확인하는 건 불필요한 행동이다.
🛠️ 리팩토링
그냥 리팩토링해버렸다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class _15703 {
private static Queue<Integer> q = new PriorityQueue<>();
private static Queue<Integer> nextQ = new ArrayDeque<>();
private static int towersCnt = 0;
private static int currentTowerHeight = 0;
public static void main(String[] args) throws IOException {
input();
while (true) {
while (!q.isEmpty()) {
int value = q.poll();
// 쌓을 수 있다면 쌓고
if (currentTowerHeight <= value) {
currentTowerHeight++;
}
// 없다면 미뤄둔다
else {
nextQ.add(value);
}
}
// 더 쌓을 수 주사위가 없다면 현재 쌓던 탑을 완성 처리
currentTowerHeight = 0;
towersCnt++;
if (nextQ.isEmpty()) {
break;
}
// 미뤄둔 주사위가 있다면 다시 쌓기
q = nextQ;
nextQ = new ArrayDeque<>();
}
System.out.println(towersCnt);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
q.add(Integer.parseInt(st.nextToken()));
}
}
}
빨라졌다.
입니다.