- 문제설명
첫번째 줄은 테스트케이스의 수, 두번째 줄 입력은 첫번째 테스트 케이스의 입력 데이터 수
각각의 테스트 데이터는 "문자 숫자"의 형태로 이루어져있다
문자가 들어오면 해당 문자가 I인지 D인지 확인하고 I이면 input, D이면 delete를 수행한다
D문자가 들어오면 숫자가 -1이면 최소값을 빼주고 1이면 최대값을 빼준다
- 실패와 원인
처음에는 두개의 우선순위 큐를 사용하여 (최댓값 정렬하는 maxQ, 최소값 정렬하는 minQ)
각각의 큐에 데이터를 저장하고 빼주는 형식으로 구현했는데
delete -1이 들어오면 최소값큐에 poll 하고 해당 값을 최대값큐에도 빼줘야한다.
하지만 이 과정인 remove(obejct)는 큐의 처음부터 해당 obejct가 있는지 확인하며
수행하기 때문에 당연히 시간초과가 난다.
(remove(object) 의 시간복잡도 O(N) 근데 이게 for문안에 들어있다?)
그래서 Map을 사용하여 삭제하려는 index를 가지고 해당 index만 삭제하도록 구현하였다.
- 구현 방법
처음에는 Node를 사용하여 index와 값을 저장하려 했지만 결국 실패하고...
블로그를 찾아보던 중
map.getOrDefault(n,0)
을 사용하여 구현하는 방법을 참고하여 구현하였다.
Map에 저장할 때 key값을 입력한 숫자로 저장하고, map.getOrDefault를 통해 갯수를 저장하였다.
getOrDefault : 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드
만약 해당 메서드를 통해 찾는 키가 없다면 0 +1을 저장한다.
만약 찾는 키가 있다면 해당 값에 +1한 값을 저장한다.
자세한 설명은 아래 코드 주석에 있다
- 코드와 주석
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class B7662 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
PriorityQueue<Integer> minQ = new PriorityQueue<>();
PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());
Map<Integer, Integer> map = new HashMap<>();
int k = Integer.parseInt(br.readLine());
for (int j = 0; j < k; j++) {
st = new StringTokenizer(br.readLine()," ");
String s = st.nextToken();
int n = Integer.parseInt(st.nextToken());
if(Objects.equals(s, "I")){
minQ.add(n);
maxQ.add(n);
// Map을 사용하여 저장하는 값을 key 값으로 두고
// 해당 값이 없으면 default 값인 0에 1을더하여 1을 저장한다
// 만약 있으면 해당 갯수에 +1
map.put(n, map.getOrDefault(n,0) +1 );
}else{
if(map.size()==0) continue;
if(n==-1){
delete(minQ,map);
}else{
delete(maxQ,map);
}
}
}
if(map.size()==0){
sb.append("EMPTY").append('\n');
}else{
// 최대값 최소값 출력
// 최소 최대값이 같으면 (최대값 poll후 size가 0이면) 최대값을 두번 출력한다
int res = delete(maxQ, map);
sb.append(res).append(" ");
if(map.size()>0) res = delete(minQ, map);
sb.append(res).append('\n');
}
}
System.out.println(sb);
}
private static int delete(PriorityQueue<Integer> queue, Map<Integer, Integer> map) {
int num;
while(true){
num = queue.poll();
// maxQ나 minQ에서 꺼낸 값이 map에 있는지 확인하고
// 없으면 계속 반복한다
int cnt = map.getOrDefault(num,0);
if(cnt == 0) continue;
// 해당 값이 1이면 제거 (해당값이 하나만 있으면)
if(cnt == 1)
map.remove(num);
else
//해당 값이 여러개면 한개 줄여서 저장
map.put(num, cnt-1);
break;
}
return num;
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[백준 java] 3425 - 고스텍 (0) | 2022.09.02 |
---|---|
[백준 java] 1654 - 랜선자르기 (0) | 2022.08.30 |
[백준 java] 1068 - 트리 (0) | 2022.08.27 |
[백준 java] 10845 - 큐 (0) | 2022.08.26 |
[백준 java] 10828 - 스택 (0) | 2022.08.26 |