Tutorial : STL Map 2 ( 원소 검색 ) timer 2s memory 1024MB

Map 의 개념을 이해했다면, 이제 Map 에서 원소를 검색하는 방법을 살펴보자.

Map 은 항상 key(순서 쌍의 앞 원소)를 기준으로 정렬하기에, 검색도 key 기준이다.

우선, 아래 코드를 보자. 실행 결과는 무엇일까?

map <int, int> m;

m[1] = 5; // m 에 { 1, 5 } 순서 쌍 삽입

if(m[2] == 5){ // { key = 2  ,  value = 5 }  인 순서 쌍이 m 에 존재하는가?
    printf("YES");
}
else{
    printf("NO");
}

실행 결과는, 당연히 NO 일 것이다.

if(m[2] == 5) 는, m 에 {2, 5} 순서 쌍이 있는지 질문하는 것이다.

하지만 m 에는 {1, 5} 순서 쌍 밖에 없으므로 NO 가 출력 된다.

여기서 중요한 점은, m[2] == 5 만 실행을 해도, 컴퓨터는 자동으로 {2, 0} 순서 쌍을 m 에 집어넣는다는 것이다!

앞서 배운 대로 m[2] = 0 이나 m.insert({2, 0}) 을 하지 않았고,

단지 m[2] == 5 인지 확인만 했는데도 {2, 0} 순서 쌍이 삽입된다.

그럼 왜 하필 { 2 , 0 } 일까? 왜 뒷 원소, 즉 value 의 값이 0 일까?

m[2] == 5 인지 확인할 때, 애초에 key 값이 2 인 순서 쌍이 없었다.

그러므로 자동으로 key = 2 인 순서 쌍이 삽입되고, value 값은 지정되지 않았기에 int 의 기본 값인 0 으로 들어가는 것이다.

그럼, 아래 코드의 실행 결과는 무엇일까?

map <int, int> m;

m[1] = 5; // m 에 { 1, 5 } 순서 쌍 삽입

if(m[2] == 0){ // { key = 2  ,  value = 0 }  인 순서 쌍이 m 에 존재하는가?
    printf("YES");
}
else{
    printf("NO");
}

정답은, YES 이다.

m[2] == 0 을 물어보는 순간, { 2, 0 } 순서 쌍이 m 에 삽입 되고,

이후에 컴퓨터는 m[2] == 0 의 참 / 거짓 여부를 판단하기 때문이다.

map 에서 특정 key 값이 있는지 확인만 해도, 순서 쌍이 자동 삽입되는 것을 알 수 있었다.

이것을 방지할 순 없을까?

이 때 쓰이는 것이 바로 find() 함수이다.

find() 함수로 key 값을 검색하면, 그 값이 들어있지 않아도 순서 쌍이 자동 삽입되지 않는다.

처음 코드와 똑같은 질문을 find() 를 이용해서 해보자.

map <int, int> m;

m[1] = 5; // m 에 { 1, 5 } 순서 쌍 삽입

if(m.find(2) != m.end()){
    printf("YES");
}
else{
    printf("NO");
}

// 출력 결과 : NO

m.find(2) 를 하면, "m 에 key 값이 2 인 순서 쌍이 존재하는가?" 라는 질문이 된다.

만약 존재한다면, m.find() 함수는 그 순서 쌍의 iterator 를 반환한다.

존재하지 않는다면, m.find() 함수는 m.end(), 즉 이 map 의 끝(end) 을 반환한다.

즉, m.find(2) == m.end() 라면 key = 2 인 순서 쌍이 없는 것이고,

반대로 m.find(2) != m.end() 라면 key = 2 인 순서 쌍이 있는 것이다.

위 두 가지 검색 방법을 최종 정리하면 아래와 같다.

find() 함수를 쓰면, 검색 이후에도 map 의 상태는 바뀌지 않기에,

map 에서 원소를 검색할 때는 find() 함수를 쓰는 것을 조금 더 권장한다.

<응용 문제>

총 Q 개의 명령이 들어온다.

int 범위의 정수들을 담는 "사전" 이 있다고 하자. 처음에 이 사전은 텅 비어있다.

입력되는 명령은 아래 3가지 형태 중 하나다.

f x : 정수 x 가 사전에 있다면 "YES (x의 개수)" 를 출력하고, 없으면 "NO" 를 출력한다.

( x 가 있는지 검사만 할 뿐, x 를 추가하는 것이 아니다. )

a x : 정수 x 를 사전에 1 개 추가한다.

c : 현재 사전에 몇 종류의 서로 다른 정수들이 있는지 출력한다.