정수형 학번(roll)과 문자열 이름(name)을 저장하는 맵(map) 자료구조가 있다고 가정해 보겠습니다. 표준 입력으로 n개의 쿼리가 주어지며, 각 쿼리는 한 줄에 두 개 또는 세 개의 요소로 구성됩니다. 첫 번째 요소는 연산 타입, 두 번째 요소는 학번이며, 타입 1 쿼리의 경우 세 번째 요소로 이름이 추가됩니다.
연산 종류
삽입(Insert): 해당 학번에 대응되는 이름을 맵에 삽입합니다.
삭제(Delete): 학번에 해당하는 항목을 맵에서 삭제합니다(존재하는 경우).
검색(Search): 학번으로 맵에서 이름을 찾습니다. 이름이 존재하면 이름을 출력하고, 없으면 "Not found"를 출력합니다.
입력 예시와 기대 출력
예를 들어 n = 8이고 쿼리가 [[1,5,"Atanu"], [1,8,"Tapan"], [1,3,"Manish"], [2,8], [1,9,"Piyali"], [3,8], [3,3], [3,5]]라면, 출력은 [Not found, Manish, Atanu]가 됩니다. 학번 8은 삭제 연산으로 인해 더 이상 존재하지 않고, 학번 3인 학생의 이름은 Manish, 학번 5인 학생의 이름은 Atanu이기 때문입니다.
문제 해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- n := 쿼리의 개수
- 키는 정수형, 값은 문자열형인 맵 m을 하나 정의합니다.
- n이 0이 될 때까지 다음을 반복합니다.
- 현재 쿼리 타입 t를 입력받습니다.
- 학번(roll)을 입력받습니다.
- t가 1이라면:
- 이름(name)을 입력받습니다.
- m[roll] := name 으로 설정합니다.
- t가 2라면:
- m[roll] := 빈 문자열("")로 설정합니다.
- 그 외의 경우(t가 3이라면):
- m[roll]이 빈 문자열이 아니면 m[roll]을 출력합니다.
- 그렇지 않으면 "Not found"를 출력합니다.
구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <iostream>
#include <map>
using namespace std;
int main() {
int n;
cin >> n;
map<int, string> m;
while (n--) {
int t;
cin >> t;
int roll;
cin >> roll;
if (t == 1) {
string name;
cin >> name;
m[roll] = name;
} else if (t == 2) {
m[roll] = "";
} else {
if (m[roll] != "")
cout << m[roll] << endl;
else
cout << "Not found" << endl;
}
}
}
입력
8 1 5 Atanu 1 8 Tapan 1 3 Manish 2 8 1 9 Piyali 3 8 3 3 3 5
출력
Not found Manish Atanu
동작 원리 살펴보기
위 코드에서 주목할 점은 C++의 map 컨테이너가 내부적으로 레드-블랙 트리(red-black tree) 기반으로 구현되어 있다는 것입니다. 덕분에 삽입, 삭제, 검색 모두 O(log n)의 시간 복잡도를 보장하며, 키(학번)를 기준으로 항상 정렬된 상태를 유지합니다.
또한 m[roll]처럼 대괄호 연산자로 접근하면 해당 키가 없을 경우 자동으로 기본값(빈 문자열)이 생성되므로, 별도의 존재 여부 확인 없이 간결하게 코드를 작성할 수 있습니다. 다만 이 특성 때문에 의도치 않게 빈 항목이 추가될 수 있으니 주의가 필요합니다.