오늘은 프로그래머스의 이중우선순위큐라는 문제를 풀어 보았다.
문제 설명은 다음과 같다.
문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어 수신 탑(높이)
I 숫자 : 큐에 주어진 숫자를 삽입합니다.
D 1 : 큐에서 최댓값을 삭제합니다.
D -1 : 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
제한사항
- operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
- operations의 원소는 큐가 수행할 연산을 나타냅니다.
- 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
위 문제는 숫자를 넣고 최댓값과 최소값을 삭제하고 연산이 끝난 후 큐에 남아있는 최대값과 최소값을 반환하는 문제이다.
위 문제를 보고 풀이를 생각해 보니 리스트를 사용하여 앞의 영어 단어가 I이면 뒤에 값을 삽입하고 D이면 분기를 나누어 최댓값과 최솟값을 제거한 뒤 리스트가 비어있지 않을 때 최댓값과 최솟값을 반환해주면 되겠다고 생각이 들었다.
위 방법으로 풀어보니 정답을 받을 수 있었다.
풀이 코드는 다음과 같다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Solution {
public int[] solution(String[] operations) {
int[] answer = { 0, 0 };
List<Integer> intList = new ArrayList<>();
for (int i = 0; i < operations.length; i++) {
String[] splitString = operations[i].split(" ");
if (splitString[0].equals("I")) {
intList.add(Integer.parseInt(splitString[1]));
} else if (!intList.isEmpty()) {
if (splitString[1].equals("1")) {
intList.remove(Collections.max(intList, null));
} else if (splitString[1].equals("-1")) {
intList.remove(Collections.min(intList, null));
}
}
}
if (!intList.isEmpty()) {
answer[0] = Collections.max(intList, null);
answer[1] = Collections.min(intList, null);
}
return answer;
}
}우선 큐가 비어있을 경우를 대비해 answer를 0 두개로 초기화해주고 정수를 담을 리스트를 생성해준다.
그리고 문자열에 저장되어 있는 연산들 만큼 반복문을 돌려준다.
반복문 안에서는 연산을 해석하기 위해 문자열을 분리해주고 앞의 문자를 확인 후 값을 넣거나 제거해주는 것을 반복한다.
반복문이 끝난 후 리스트가 비어있지 않다면 최대값과 최소값을 answer에 넣어주고 비어있다면 그대로 반환을 해준다.
이렇게 풀게 되면 정답을 받을 수 있다.
