728x90
반응형
2024.08.15기준 - 골드4
백준, BEAKJOON, BOJ, JAVA, 자바
풀이
이 문제는 주어진 키워드가 I 또는 D가 들어올 때, I n 이면 n을 추가 D 1 이면 최댓값을 D -1이면 최솟값을 제거 후 최댓값과 최솟값을 출력하는 문제입니다.
이 문제는 시간초과가 많이 나와 여러가지 방법을 찾다가 TreeMap을 활용하여 문제에 접근하게 되었습니다.
처음엔 priorityqueue를 이용해 오름차순, 내림차순의 큐를 2개 생성해 해당 값을 제거할 때, remove를 사용해 제거를 진행했지만 시간초과가 나와 여러가지 방법을 생각해보았습니다.
우선 TreeMap에 대한 설명을 하자면
- 키의 자동 정렬
- TreeMap은 키를 기준으로 자동으로 정렬을 합니다.
- 기본적으로 오름차순으로 정렬되지만, 커스텀 Comparator를 사용하면 정렬 방식을 변경할 수 있습니다.
- 레드 - 블랙 트리 기빈
- 내부적으로 레드-블랙 트리 구조를 사용하여 효울적인 검색, 삽입, 삭제 연산을 제공해줍니다.
1. TreeMap을 생성 후 키워드에 I가 들어온다면 switch문을 통해 map에 값을 추가 시켜줍니다.
(map.getOrDefault() 메서드를 활용해 값이 있다면 해당 값을 없다면 0을 기반으로 +1을 해줍니다.)
case "I": // 수를 map에다가 저장
map.put(num, map.getOrDefault(num, 0) + 1);
break;
2. 키워드에 D가 들어온다면 1 과 -1를 참조해 최솟값 또는 최댓값을 제거해주도록 합니다.
TreeMap에는 lastKey()와 firstKey()메서드가 존재합니다. 그래서 최댓값과 최솟값의 수를 한 번에 찾을 수 있습니다.
key = num == 1 ? map.lastKey() : map.firstKey();
그래서 map이 비어있지 않다면 값을 제거하는 데, 그 개수가 0이 된다면 map에서 제거를 해줍니다.
case "D": // 최솟값 or 최댓값 제거
if (!map.isEmpty()) { // map에 값이 있다면
// num 이 1이면 최댓값을 -1이면 최솟값의 key를 저장.
key = num == 1 ? map.lastKey() : map.firstKey();
// map.put()은 값이 변환되기 이전에 값을 반환하기 때문에 참조하는 key의 개수가 1이라면 제거를 해줍니다.
if (map.put(key, map.get(key) - 1) == 1) {
map.remove(key);
}
}
break;
3. 이렇게 정리된 map을 통해 비어있다면 "EMPTY"를 출력 아니라면 최댓값과 최솟값을 출력합니다.
if (map.isEmpty()) { // map이 비어있다면
sb.append("EMPTY\n");
} else { // map에 값이 있다면
sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
}
코드
package Main;
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));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
String s;
int n, num, key;
StringTokenizer st;
TreeMap<Integer, Integer> map; // 들어오는 수를 담을 treemap
while (t-- > 0) {
n = Integer.parseInt(br.readLine());
map = new TreeMap<>();
while (n-- > 0) {
st = new StringTokenizer(br.readLine());
s = st.nextToken();
num = Integer.parseInt(st.nextToken());
switch (s) {
case "I": // 수를 map에다가 저장
map.put(num, map.getOrDefault(num, 0) + 1);
break;
case "D": // 최솟값 or 최댓값 제거
if (!map.isEmpty()) { // map에 값이 있다면
// num 이 1이면 최댓값을 -1이면 최솟값의 key를 저장.
key = num == 1 ? map.lastKey() : map.firstKey();
// map.put()은 값이 변환되기 이전에 값을 반환하기 때문에 참조하는 key의 개수가 1이라면 제거를 해줍니다.
if (map.put(key, map.get(key) - 1) == 1) {
map.remove(key);
}
}
break;
}
}
if (map.isEmpty()) { // map이 비어있다면
sb.append("EMPTY\n");
} else { // map에 값이 있다면
sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
728x90
반응형
'코딩테스트 일기 (BAEKJOON)' 카테고리의 다른 글
BEAKJOON / 백준 - JAVA 3097번 산책 경로 (0) | 2024.08.17 |
---|---|
BEAKJOON / 백준 - JAVA 9291번 스도쿠 채점 (0) | 2024.08.16 |
BEAKJOON / 백준 - JAVA 30618번 donstructive (0) | 2024.08.14 |
BEAKJOON / 백준 - JAVA 9613번 GCD 합 (0) | 2024.08.13 |
BEAKJOON / 백준 - JAVA 18511번 큰 수 구성하기 (0) | 2024.08.12 |