[BOJ 1920] 수찾기, set lower_bound()

https://www.acmicpc.net/problem/1920

이번에 해결한 문제는 Baekjoon의 1920번 "수 찾기" 문제다. 이 문제는 N개의 정수 집합이 주어졌을 때, 주어진 수들이 해당 집합에 존재하는지 확인하는 프로그램을 작성하는 것이다. 문제 자체는 단순해 보였지만, 중간에 실수를 발견하고 해결하는 과정이 있었다.

 

문제 설명

 N개의 정수가 주어진 후, M개의 다른 정수들이 그 N개의 집합에 포함되어 있는지 확인하면 된다. 예를 들어, N개의 정수 집합이 `4, 1, 5, 2, 3`이고, 확인해야 할 수들이 `1, 3, 7, 9, 5`라면, 각 수가 존재하는지 여부를 1 또는 0으로 출력하면 되는 문제다.

 

처음 작성한 코드

처음에는 이 문제를 `set` 자료구조로 쉽게 해결할 수 있다고 생각했다. `set`은 중복을 허용하지 않고, 내부적으로 정렬된 상태로 저장되므로 `lower_bound()` 메소드를 사용하면 쉽게 원하는 수가 있는지 확인할 수 있을 것이라 판단했다.

그래서 아래와 같은 방식으로 코드를 작성했다:

#include <iostream>
#include <set>

using namespace std;

int n; //n개의 정수
set<int> s; 
int m; // m개의 확인하는 수

void input(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        s.insert(temp);
    }
}

void solve(int num){
    if(s.lower_bound(num) != s.end()){
        cout << "1\n";
    } else {
        cout << "0\n";
    }
}

int main(){
    input();
    cin >> m;
    for(int i = 0; i < m; i++){
        int temp;
        cin >> temp;
        solve(temp);
    }
}

 이 코드를 작성한 후 테스트 입력을 여러 가지로 해보았다. 그 중 입력이 `5, 0, 5, 6, 0, 89`일 때, 예상과 다르게 `0`이 `set`에 없는데도 1로 출력되는 문제가 발생했다. 분명히 0은 집합에 없는데, 왜 있는 것처럼 나오는 걸까?

원인 

 문제의 원인은 `lower_bound()` 함수의 사용 방식에 있었다. `lower_bound()`는 `num` 이상의 첫 번째 값을 반환하는데, 이 값이 `num`과 정확히 같은 값인지 여부는 확인하지 않고 있었다. `set`에서 `lower_bound()`가 반환한 이터레이터가 `num`보다 크기만 해도 이 조건이 참이 되어버리는 것이다. 예를 들어, `lower_bound(0)`을 호출했을 때, 0보다 큰 첫 번째 값인 1을 가리키는 이터레이터가 반환되므로, 이 값이 존재한다고 잘못 판단하는 것이다.

 

해결

문제를 해결하기 위해서는 `lower_bound()`로 반환된 이터레이터가 `num`과 정확히 일치하는지 확인하는 추가 검증이 필요했다. 그래서 `lower_bound()`로 반환된 이터레이터가 `set.end()`가 아닌 경우, 해당 값이 `num`과 일치하는지를 확인하는 조건을 추가했다.

void solve(int num){
    auto it = s.lower_bound(num);
    if(it != s.end() && *it == num){
        cout << "1\n";
    } else {
        cout << "0\n";
    }
}