문제 소개
정수형 데이터를 저장하는 세트(Set) 자료구조가 있다고 가정해 보겠습니다. 표준 입력으로 n개의 쿼리가 주어지며, 각 쿼리는 한 줄에 두 개의 값으로 구성됩니다. 첫 번째 값은 연산 종류를 나타내는 연산자이고, 두 번째 값은 처리할 요소입니다.
각 연산의 의미는 다음과 같습니다.
- 삽입(Insert): 해당 요소를 세트에 추가합니다.
- 삭제(Delete): 해당 요소가 세트에 존재하면 제거합니다.
- 탐색(Search): 해당 요소가 세트에 있는지 확인하여, 존재하면 "Yes"를, 없으면 "No"를 출력합니다.
예를 들어 입력이 n = 7이고 쿼리가 [[1,5], [1,8], [1,3], [2,8], [1,9], [3,8], [3,3]]이라면, 출력은 [No, Yes]가 됩니다. 그 이유는 8은 이미 삭제되어 세트에 없지만, 3은 여전히 존재하기 때문입니다.
해결 접근 방식
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 세트 s를 선언합니다.
- s를 순회할 때 사용할 반복자(iterator) it을 선언합니다.
- 쿼리의 개수를 q에 저장하고, q번만큼 반복합니다.
- 반복마다 쿼리 유형(qt)과 값(x)을 입력받습니다.
- qt의 값에 따라 분기 처리합니다.
- qt가 1인 경우: insert(x)로 x를 세트에 삽입합니다.
- qt가 2인 경우: erase(x)로 세트에서 x를 삭제합니다. 요소가 없어도 안전하게 동작합니다.
- qt가 3인 경우: find(x)를 호출하여 결과를 반복자에 저장합니다. 반환된 반복자가 s.end()와 같다면 요소가 존재하지 않으므로 "No"를, 그렇지 않다면 "Yes"를 출력합니다.
핵심 포인트
C++ STL의 set.find(x) 함수는 찾는 값이 없을 경우 세트의 끝을 가리키는 반복자(end())를 반환합니다. 따라서 이 값을 비교하는 것만으로도 원소의 존재 여부를 손쉽게 판별할 수 있습니다. 또한 set은 내부적으로 균형 이진 탐색 트리(레드-블랙 트리)로 구현되어 있어, 삽입·삭제·탐색 모두 O(log N)의 시간 복잡도를 가집니다.
예제 코드
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <iostream>
#include <set>
using namespace std;
int main(){
set<int> s;
set<int>::iterator it;
int q, x, qt;
cin >> q;
while(q--){
cin >> qt >> x;
switch(qt){
case 1:
s.insert(x);
break;
case 2:
s.erase(x);
break;
case 3:
it = s.find(x);
if(it == s.end())
cout << "No" << endl;
else
cout << "Yes" << endl;
break;
}
}
return 0;
}실행 결과
입력
7 1 5 1 8 1 3 2 8 1 9 3 8 3 3
출력
No Yes
마무리
이처럼 STL의 set 컨테이너는 insert(), erase(), find() 메서드를 통해 중복 없는 데이터 관리와 빠른 검색 기능을 손쉽게 제공합니다. 특히 find()와 end()의 비교 패턴은 STL 컨테이너를 다룰 때 자주 사용되는 핵심 기법이므로 꼭 익혀두시길 권장합니다.