99클럽 코테 스터디 10일차 TIL 이중우선순위큐
📝 문제
|
|
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
🔥 시도해본 접근 방식
본 문제는 입력으로 들어온 문자열 배열을 해석하여
1. 숫자를 삽입
2. 최솟값 제거
3. 최댓값 제거
위 명령을 큐를 사용하여 수행하면서 [최댓값, 최솟값]배열을 출력하면 될 것이라고 생각하고 접근하였다.
PriorityQueue를 사용하면 최소값을 제거하는 작업은 단순히 poll()을 해주면 되지만,
최댓값을 제거하는 작업은 효율적인 방법이 떠오르지 않아 우선 새로운 PriorityQueue를 선언해 기존 PriorityQueue에서 size - 1 까지 값을 뽑아내어 넣어주는 방식으로 적용하였다.
1️⃣ 첫번째 시도
import java.util.PriorityQueue;
class Solution {
public static int[] solution(String[] operations) {
// 힙 선언
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (String o : operations) {
// 큐에서 최대값을 삭제한다.
if (!pq.isEmpty() && o.equals("D 1")) {
PriorityQueue<Integer> newPq = new PriorityQueue<>();
for (int i = 0; i < pq.size() - 1; i++) {
newPq.offer(pq.poll());
}
pq = newPq;
}
// 큐에서 최소값을 삭제한다.
else if (!pq.isEmpty() && o.equals("D -1")) {
pq.poll();
}
// 큐에 숫자를 삽입힌다.
else if (o.startsWith("I")) {
int i = Integer.parseInt(o.substring(2));
pq.offer(i);
}
}
int size = pq.size();
int[] answer = new int[]{0, 0};
for (int i = 0; i < size; i++) {
int value = pq.poll();
if (i == 0) {
answer[1] = value;
} else if (i == n - 1) {
answer[0] = value;
}
}
return answer;
}
}위와 같이 코드를 작성하여 제출하였지만 테스트 케이스 3개에서 통과되지 못하고 실패하였다.
코드를 실행 하였을때, 입력으로 받은 문자열 배열대로 숫자 입력, 제거 동작이 문제없이 잘 작동하는 것으로 보여지는데 어떤것을 놓치고 있는지 출력을 프린트 해보았더니
입력이 ["I 1", "I 3", "I 5", "I 7", "I 9", "D -1", "D -1", "D 1", "I 2", "D 1", "D 1"]와 같을 때 "D 1" 부분에서 [5, 7, 9] -> [5] 와같이 변하는 결함을 발견하였고 for문의 pq.size()가 반복됨에 따라 값이 변하는 문제가 있음을 깨달았다.
2️⃣ 두번째 시도
import java.util.PriorityQueue;
class Solution {
public static int[] solution(String[] operations) {
// 힙 선언
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (String o : operations) {
// 큐에서 최대값을 삭제한다.
if (!pq.isEmpty() && o.equals("D 1")) {
PriorityQueue<Integer> newPq = new PriorityQueue<>();
int size = pq.size();
for (int i = 0; i < size - 1; i++) {
newPq.offer(pq.poll());
}
pq = newPq;
}
// 큐에서 최소값을 삭제한다.
else if (!pq.isEmpty() && o.equals("D -1")) {
pq.poll();
}
// 큐에 숫자를 삽입힌다.
else if (o.startsWith("I")) {
int i = Integer.parseInt(o.substring(2));
pq.offer(i);
}
}
int size = pq.size();
int[] answer = new int[]{0, 0};
for (int i = 0; i < size; i++) {
int value = pq.poll();
if (i == 0) {
answer[1] = value;
} else if (i == n - 1) {
answer[0] = value;
}
}
return answer;
}
}따라서 다음과 같이 코드를 수정하였고 다시 제출해보았지만 결과는 동일하였다.
긴 시간 고민에도 원인을 찾을 수 없어 반례 하나를 찾아보았고, 원인을 알 수 있었다.
만약 큐의 사이즈가 1일 때 내 코드는 항상 [0, 최솟값]을 리턴할 것이다 하지만 이 경우에는 최댓값과 최솟값이 같은 값으로 리턴되어야 했다는 것을 깨닫고 코드를 보완하였다.
✨ 성공 코드
import java.util.PriorityQueue;
class Solution {
public static int[] solution(String[] operations) {
// 힙 선언
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (String o : operations) {
// 큐에서 최대값을 삭제한다.
if (!pq.isEmpty() && o.equals("D 1")) {
PriorityQueue<Integer> newPq = new PriorityQueue<>();
int size = pq.size();
for (int i = 0; i < size - 1; i++) {
newPq.offer(pq.poll());
}
pq = newPq;
}
// 큐에서 최소값을 삭제한다.
else if (!pq.isEmpty() && o.equals("D -1")) {
pq.poll();
}
// 큐에 숫자를 삽입힌다.
else if (o.startsWith("I")) {
int i = Integer.parseInt(o.substring(2));
pq.offer(i);
}
}
int size = pq.size();
int[] answer = new int[]{0, 0};
for (int i = 0; i < size; i++) {
int value = pq.poll();
if (i == 0) {
answer[1] = value;
// 큐의 사이즈가 1일 수도 있으므로 최댓값도 갱신해준다.
answer[0] = value;
} else if (i == size - 1) {
answer[0] = value;
}
}
return answer;
}
}10 회차 까지 문제풀이를 하면서 문제 자체에 대한 이해도가 조금 부족하다는 느낌을 받았다.
다음 부터는 문제에 대해 부족함 없이 이해하기 위한 노력을 많이 기울여야 할 것 같다.
사실 내 풀이는 문제의 힌트인 이중우선순위큐의 목적과는 맞지 않은 풀이였다고 생각되는데 다른사람의 풀이를 보고 개인적으로 목적에 가장 부합한 풀이라고 생각하는 풀이는 다음과 같다.
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
public int[] solution(String[] arguments) {
MidV q = new MidV();
for(int i = 0; i < arguments.length; i++){
String[] commend = arguments[i].split(" ");
int v = Integer.parseInt(commend[1]);
if(commend[0].equals("I")){
q.push(v);
}else{
switch (v){
case 1 : q.removeMax();
break;
case -1: q.removeMin();
break;
}
}
}
int[] aw = new int[]{q.getMaxValue(),q.getMinValue()};
return aw;
}
}
class MidV{
private PriorityQueue<Integer> leftHeap;
private PriorityQueue<Integer> rightHeap;
public MidV(){
leftHeap = new PriorityQueue<>(10,Collections.reverseOrder());//최대값;
rightHeap = new PriorityQueue<>();//최소값
}
public void push(int v){
leftHeap.add(v);
}
public void removeMax(){
while(!rightHeap.isEmpty()){
leftHeap.add(rightHeap.poll());
}
leftHeap.poll();
}
public void removeMin(){
while(!leftHeap.isEmpty()){
rightHeap.add(leftHeap.poll());
}
rightHeap.poll();
}
public int getMaxValue(){
if(leftHeap.size() == 0 && rightHeap.size() == 0)
return 0;
while(!rightHeap.isEmpty()){
leftHeap.add(rightHeap.poll());
}
return leftHeap.peek();
}
public int getMinValue(){
if(leftHeap.size() == 0 && rightHeap.size() == 0)
return 0;
while(!leftHeap.isEmpty()){
rightHeap.add(leftHeap.poll());
}
return rightHeap.peek();
}
}