이 문제에서는 Q개의 쿼리가 주어지며, 각 쿼리는 다음 세 가지 유형 중 하나입니다.
- 쿼리 1: 리스트에 숫자 N을 추가합니다.
- 쿼리 2: 리스트에서 숫자 N을 삭제합니다.
- 쿼리 3: 리스트에 있는 요소들의 최댓값과 최솟값의 차이를 반환합니다.
이 글에서는 C++로 이러한 쿼리를 처리하여 요소를 추가·삭제하고, 최댓값과 최솟값의 차이를 구하는 프로그램을 만드는 방법을 알아보겠습니다.
문제 설명
리스트에 대해 수행할 Q개의 쿼리가 주어집니다. 쿼리는 요소 추가, 요소 삭제, 그리고 리스트 내 최댓값과 최솟값의 차이를 구하는 세 가지 유형으로 구성됩니다. 쿼리를 순서대로 처리해 리스트를 구성한 뒤, 마지막에 최댓값과 최솟값의 차이를 계산하면 됩니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: Q = 6
Query(1, 4) → 4 추가
Query(1, 9) → 9 추가
Query(1, 6) → 6 추가
Query(2, 4) → 4 삭제
Query(1, 3) → 3 추가
Query(3) → 차이 반환
출력: 6
설명
모든 쿼리를 처리한 후 리스트는 {9, 6, 3}이 됩니다.
- 최댓값 → 9
- 최솟값 → 3
- 차이 → 9 − 3 = 6
풀이 접근법 1: 배열 사용
가장 단순한 방법은 각 쿼리를 직접 처리하는 것입니다. 다음 단계를 따릅니다.
- 배열을 초기화합니다.
- 쿼리 유형 1이면 배열에 요소를 추가합니다.
- 쿼리 유형 2이면 배열에서 해당 요소를 삭제합니다.
- 쿼리 유형 3이면 최댓값과 최솟값의 차이를 계산해 반환합니다.
예제 코드
#include <iostream>
using namespace std;
int arr[100];
int idx = 0;
void solveQuery(int type, int item) {
if (type == 1) {
arr[idx++] = item;
}
else if (type == 2) {
for (int i = 0; i < idx; i++) {
if (arr[i] == item) {
for (int j = i; j < idx - 1; j++)
arr[j] = arr[j + 1];
idx--;
break;
}
}
}
else if (type == 3) {
int maxVal = arr[0], minVal = arr[0];
for (int i = 1; i < idx; i++) {
if (arr[i] > maxVal) maxVal = arr[i];
if (arr[i] < minVal) minVal = arr[i];
}
cout << "The difference between the maximum and minimum elements is "
<< (maxVal - minVal);
}
}
int main() {
int Q = 6;
int query[6][2] = {{1, 4}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
for (int i = 0; i < Q; i++) {
solveQuery(query[i][0], query[i][1]);
}
return 0;
}
출력
The difference between the maximum and minimum elements is 6
풀이 접근법 2: set(자가 균형 이진 탐색 트리) 사용
단순 배열 대신 다른 자료구조를 활용하면 검색 과정을 더 효율적으로 만들 수 있습니다. 자가 균형(self-balancing) 이진 탐색 트리를 사용하면 최댓값은 항상 정렬된 데이터의 끝(rbegin() 메서드로 접근)에 있고, 최솟값은 항상 시작(begin() 메서드로 접근)에 있으므로 매우 빠르게 조회할 수 있습니다.
C++에서는 STL의 set 컨테이너가 레드-블랙 트리 기반의 자가 균형 이진 탐색 트리로 구현되어 있어 이를 그대로 활용할 수 있습니다. 삽입과 삭제는 O(log N), 최댓값·최솟값 조회는 O(1)의 시간 복잡도를 가집니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
set<int> myList;
void solveQuery(int type, int num) {
if (type == 1) {
myList.insert(num);
}
else if (type == 2) {
myList.erase(num);
}
else if (type == 3) {
int maxVal = *myList.rbegin();
int minVal = *myList.begin();
cout << "The difference between the maximum and minimum elements is "
<< (maxVal - minVal);
}
}
int main() {
int Q = 6;
int query[6][2] = {{1, 4}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
for (int i = 0; i < Q; i++) {
solveQuery(query[i][0], query[i][1]);
}
return 0;
}
출력
The difference between the maximum and minimum elements is 6
마무리
배열 기반 구현은 직관적이지만 삽입·삭제 시 최악의 경우 O(N)의 시간이 소요될 수 있습니다. 반면 set을 사용하면 모든 연산을 O(log N) 안에 처리할 수 있어, 쿼리 수가 많거나 데이터 크기가 클 때 훨씬 효율적인 선택입니다.