해독부터 어려운 문제다..
남은 고용 해야하는 사람 수 < candidate
인 경우 전체 배열에서 가장 적은 비용을취한다.candidate의 용도를 이해하는 게 어려웠다. ㅠ
candidate가 3인경우 앞에서 3명, 뒤에서 3명 중 가장 적은 비용을 취하면 된다.두 개의 우선순위 큐를 이용하여 문제를 풀어나간다.
우선순위 큐는 삽입 순서에 상관 없이 deque
될 때 우선순위에 맞게 나간다.
우선순위는 프로그래머가 결정할 수 있지만, 이 문제에서는 우선순위를 변경하지 않아도 된다.
그 이유는, 그림의 natural ordering
을 살펴보면,
우선순위가 Collection.sort
로 자동 정렬되어 deque
할 때 작은 순서대로 빠져나간다.
문제에서 각 candidate 중 적은 비용을 취하므로 우선순위를 따로 조작하지 않아도된다.
변수 선언
public long totalCost(int[] costs, int k, int candidates) {
PriorityQueue<Integer> pq1 = new PriorityQueue<>();
PriorityQueue<Integer> pq2 = new PriorityQueue<>();
int front =0;
int end =costs.length-1;
long sum =0;
...
- p1
: 앞에서부터 candidate 만큼을 저장하는 우선순위 큐
- p2
: 뒤에서부터 candidate 만큼을 저장하는 우선순위 큐
- front
: p1에 사용할 인덱스
- end
: p2에 사용할 인덱스
- sum
: k명의 고용 비용을 저장하는 변수
우선순위 큐 저장 & 적은 비용 찾기
...
while(k-- >0){
while(pq1.size()<candidates && front<=end){
pq1.offer(costs[front++]);
}
while (pq2.size()<candidates&&front<=end){
pq2.offer(costs[end--]);
}
int v1 = pq1.size()>0?pq1.peek():Integer.MAX_VALUE;
int v2 = pq2.size()>0?pq2.peek():Integer.MAX_VALUE;
if(v1<=v2){
sum+=v1;
pq1.poll();
}
else{
sum+=v2;
pq2.poll();
}
}
return sum;
while
문 내의front<=end
조건이 중요하다고 생각한다.
front>end
인 경우, 이미 q2에 저장된 원소를 q1에 삽입하거나 그 반대의 경우가 이루어질 수 있기 때문에 유효한 답을 낼 수 없다.
그림으로 알아보자!
k=2일 때, q2
의 2가 선택되고, k=1로 넘어간다.
이때, q2가 추가되지 않는데, front <= end
의 조건을 충족하지 못했기 때문이다.
class Solution {
public long totalCost(int[] costs, int k, int candidates) {
PriorityQueue<Integer> pq1 = new PriorityQueue<>();
PriorityQueue<Integer> pq2 = new PriorityQueue<>();
int front =0;
int end =costs.length-1;
long sum =0;
while(k-- >0){
while(pq1.size()<candidates && front<=end){
pq1.offer(costs[front++]);
}
while (pq2.size()<candidates&&front<=end){
pq2.offer(costs[end--]);
}
int v1 = pq1.size()>0?pq1.peek():Integer.MAX_VALUE;
int v2 = pq2.size()>0?pq2.peek():Integer.MAX_VALUE;
if(v1<=v2){
sum+=v1;
pq1.poll();
}
else{
sum+=v2;
pq2.poll();
}
}
return sum;
}
}
내 힘으로 못 풀었다... 될 것 같으면서도 안 됐다.
남은 고용인원 수 < candidate인 조건이 내 발목을 잡았다.
해답을 보는 일이 많아지니 내 문제점이 보였다.
문제 풀이를 한 바퀴 더 꼬아서 생각하다 보니 코드도, 생각도 산으로 간다.
앞으로 문제 풀 때 직관적으로 다가가려고 노력해야겠다.
Crocus - 우선순위 큐 개념 (1)
ynzu - [JAVA] Priority Queue 우선순위 조건 변경하기