문제 탐색하기
입력값 자료 정리
- T는 이후 입력이 진행될 테스트케이스의 개수이다
- n은 이후 들어올 명령어 집합의 개수이다
- n만큼 들어오는 각 두 수의 앞은 명령어, 이후는 명령어에 맞는 수이다
해결방법 추론
- 문제의 이름이 이중 우선순위 큐이기 때문에, 쉽게 우선순위 큐를 떠올릴 수 있었다
- 우선순위 큐의 remove를 사용하면 O(n)만큼 탐색하기 때문에 시간초과가 발생할 수 있어 제외하였다
- remove를 사용 못하면 최소큐와 최대큐를 각각 둬서 관리하자고 생각하였다
- 최대 큐는 내림차순 정렬 설정을 해주면 된다
- 입력할 때는 두 큐에 모두 넣어주고, 뺄때는 최댓값과 최솟값 큐만 각각 뺴준다
- 그리고 출력할 때 둘다 비어있거나 같다면 EMPTY 출력,
둘중 한쪽이 비어있으면 하나의 큐가지고 출력,
둘다 안 비어있으면 각각 하나씩 뽑아서 최댓값 최솟값을 출력하면 된다!
시간복잡도 계산
- 이렇게 했을 때, 시간복잡도는 T x k 만큼의 시간복잡도가 발생할 것이다
- 따라서 시간제한인 6초안에는 무조건 들어올 수 있다
코드 설계하기
입력값 상태 관리하기
- T와 n은 변수로 받아 관리하며, StringTokenizer로 들어온 명령어와 수도 각각의 지역변수로 관리한다
- 이어서 최대큐와 최소큐에 명령어에 맞춰서 넣어주거나 빼주면 된다
I 명령 설계
- I이면 최소큐와 최대큐에 num을 넣어주도록 설계하였다
D 명령 설계
- 1이면 최댓값을 빼야하니 최대큐를 poll하고, -1이면 최솟값을 빼야하니 최솟값을 poll한다
출력 설계
- 일단 둘다 비어있으면 당연히 EMPTY다.
- 한쪽이 비어있으면 다른 한쪽에서 충족시키면 될 것이라고 생각하였다
- 그래서 한쪽 큐 가지고 크기만큼 탐색해서 최댓값과 최솟값을 출력한다
- 만약 둘다 비어있지 않다면 각각에서 하나씩 뽑아 최댓값 최솟값으로 출력하면 된다
- 여기서 한가지 잘못 생각하고 입력 예제에 맞추는 잘못된 로직을 짰는데,
두 큐의 peek가 같으면 EMPTY를 출력하도록 했다 - 왜냐하면 첫번째 예제에서 두 큐의 값이 같고 실제 이중 우선순위 큐에는 하나만 남은 상황이었다
- 이것을 예제에 맞추기 위해 이 경우도 EMPTY로 출력하도록 했다
시도 회차 수정
1, 3회차 시도 실패
- 당연히 논리적이지 않게 단순 예제입력에 맞추는 코드는 틀릴 수 밖에 없다
- 20%정도에서 틀렸습니다들 받았다
- 우선순위 큐만을 가지고 하자니 몇가지 경우에서 문제가 생길 수 있는 것을 알게 되었다
- 먼저 이중 우선순위 큐에 하나의 수만 남은 경우 충분히 문제가 발생할 수 있다
- 또한 두 큐는 사실 같은 하나의 큐로 봐야한다.
단지 최대값과 최솟값을 편하게 보기 위해 두개로 나눈 것 뿐이다 - 하지만 입력은 같이 들어가나 출력은 하나만 된다.
따라서 여기서 두 큐간의 데이터의 상태 관리가 꼬여버리는 문제가 발생한다. - 데이터가 꼬임에 따라 출력도 이상하게 된다. 따라서 1,3회차는 틀리게 되었다
- 3회차는 단순히 long타입으로 변하지 않은게 문제인가 싶어서 했다가 똑같이 틀린 코드다
2회차 시도 실패
- 2회차는 한쪽 큐에다가 다 몰아 넣는 방법을 선택하였다
- 만약 현재 숫자보다 최대 큐에 있는 값이 더 크다면 최소 큐에다가 넣는 것이다
- 당연히 이렇게 되면 도중에 삭제 요청이 올때 이상하게 되어버린다
- 이번 시도는 1%에서 틀려버렸다
4회차 시도 전 재설계
- 이중 우선순위큐를 사용하면 한 절반은 충족을 시키는데 뭔가 2% 부족한 느낌이다
- 추가적인 자료구조를 사용하거나 아니면 이중 우선순위 큐처럼 동작하는
하나의 자료구조를 찾아야 한다
4회차 재설계
새로운 자료구조
- 새로운 자료구조로 Map을 찾게 되었다.
- 이중에서도 자동 정렬되는 TreeMap을 사용하게 되었다
- 정렬이 자동으로 된다고 한다면 우선순위큐의 역할을 할 수 있고,
또한 Map은 해시함수기 때문에 시간복잡도의 큰 영향을 주지 않는다
미리 알고가야하는 개념/주의점
- TreeMap의 내장 함수를 사용하려면 다형성을 이용한 Map 타입을 사용하는 것이 아니라
TreeMap 타입으로 지정해야 한다 - lastKey()는 최댓값 firstKey()는 최댓값이 될 것이다
- map.put()의 결과는 해당 key의 이전 value를 리턴한다
I 명령 설계
- I인 경우 map에 해당 num을 key로 넣어준다
- map.getOrDefault를 사용하여 key값이 등록 안 된 경우를 방지한다
D 명령 설계
- D 명령이 들어왔는데 map이 비어있는 경우 그냥 스킵해준다.
- continue로 다음 작업을 건너뛰자
- map에 값이 있는경우 1인경우와 아닌 경우로 나누어서 비교한다
- 1인 경우는 lastKey()를 remove하고, 아닌 경우는 firstKey()를 remove하면 된다
- 이때 map.put()을 이용하여 각각의 value를 -1만큼 감소시킨다.
- 그리고 그 반환값이 1인경우만 remove한다
- 왜냐하면 같은 크기의 값이 들어오면 그 개수가 늘어나게 될 것이다
- 하지만 단순히 remove를 한다면 2개이상이 들어있더라도 다 날려버리는 문제가 발생하여,
값을 갱신했을 때, 이전 value가 1인 경우만 remove한다
출력 설계
- map이 비어있으면 EMPTY를 출력하고,
아니면 최댓값 lastKey()와 최솟값 firstKey()를 출력하면 정답이 된다
알고리즘/코딩 테스트 주의점
- 예제 입력에 단순 종속된 코드는 짜지 말자!
- 꼭 논리적인 설계에 입각한 코드를 짜도록 하자
- 현재 자료구조로 뭔가 부족하다는 느낌이 든다면, 새로운 자료구조 사용에 대한 고민을 꼭 하자
정답 코드
(1, 3회차 시도 실패)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
PriorityQueue<Integer> small = new PriorityQueue<>();
PriorityQueue<Integer> big = new PriorityQueue<>(Collections.reverseOrder());
int n = Integer.parseInt(br.readLine());
for (int j = 0; j < n; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
char s = st.nextToken().charAt(0);
int num = Integer.parseInt(st.nextToken());
if(s == 'I'){
small.add(num);
big.add(num);
}else{
if(num == 1){
big.poll();
}else{
small.poll();
}
}
}
if(small.isEmpty() && big.isEmpty() || small.peek() == big.peek()){
bw.write("EMPTY\n");
}else if(small.isEmpty()){
bw.write(big.poll());
while(big.size() != 1){
big.poll();
}
bw.write(" " + big.poll()+"\n");
}else if(big.isEmpty()){
int tmp = small.poll();
while(small.size() != 1){
small.poll();
}
bw.write(small.poll() + " " + tmp+"\n");
}else{
bw.write(big.poll() + " " + small.poll() + "\n");
}
}
br.close();
bw.close();
}
}
1, 3회차는 비슷해서 1회차만 가져왔습니다
(2회차 시도 실패)
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
* - 고민과 풀이:
*
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
PriorityQueue<Integer> small = new PriorityQueue<>();
PriorityQueue<Integer> big = new PriorityQueue<>(Collections.reverseOrder());
int n = Integer.parseInt(br.readLine());
for (int j = 0; j < n; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
char s = st.nextToken().charAt(0);
int num = Integer.parseInt(st.nextToken());
if(s == 'I'){
while(!big.isEmpty() && num > big.peek()){
small.add(big.poll());
}
big.add(num);
}else{
if(num == 1){
if(!big.isEmpty()){
big.poll();
}
}else{
if(!small.isEmpty()){
small.poll();
}
}
}
}
if(small.isEmpty() || big.isEmpty()){
bw.write("EMPTY\n");
}else{
bw.write(big.poll() + " " + small.poll() + "\n");
}
}
br.close();
bw.close();
}
}
(4회차 시도 성공)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
TreeMap<Integer, Integer> map = new TreeMap<>();
int n = Integer.parseInt(br.readLine());
for (int j = 0; j < n; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
char s = st.nextToken().charAt(0);
int num = Integer.parseInt(st.nextToken());
if(s == 'I'){
map.put(num, map.getOrDefault(num, 0) + 1);
}else{
if(map.isEmpty()){
continue;
}
if(num == 1){
if(map.put(map.lastKey(), map.get(map.lastKey())-1) == 1){
map.remove(map.lastKey());
}
}else{
if(map.put(map.firstKey(), map.get(map.firstKey())-1) == 1){
map.remove(map.firstKey());
}
}
}
}
if(map.isEmpty()){
bw.write("EMPTY\n");
}else{
bw.write(map.lastKey() + " " + map.firstKey()+"\n");
}
}
br.close();
bw.close();
}
}
문제 링크
Software Developer