[C/C++] 숫자 카드 2 (백준 10816)

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

입력

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

 

출력

3 0 0 1 2 0 0 2

풀이

숫자 카드 1과 별반 다를 거 없어 보여서 처음에는 사실 이분 탐색을 이용해서 풀어보았다습니다. 근데 그렇게 간단한 문제가 아니었습니다... 두 가지 코드를 써보았는데

void binary_search_mine(long long min, long long max, long long value){
    if(min > max) return;
    long long middle = (min + max)/2;

    if(value > first[middle]){
        binary_search_mine(middle+1,max,value);
    }
    else if(value < first[middle]){
        binary_search_mine(min,middle-1,value);
    }
    else{
        cnt++;
        binary_search_mine(middle+1,max,value);
        binary_search_mine(min,middle-1,value);
    }

}

이게 최초 코드입니다. binary_search를 직접 구현하여 전역 변수인 배열을 사용하여 찾는 값이 중간 인덱스와 비교를 하여 수를 찾으면 그 수를 기준으로 다시 탐색을 하는 식으로 진행을 하려고 했는데...

이렇게 되면 결국 전체를 탐색하게 되어 시간초과가 무조건 일어날 수 밖에 없어져서 다른 방법으로 바꾸게 되었습니다.

void binary_search_mine(long long min, long long max, long long value){
    if(min > max) return;
    long long middle = (min + max)/2;

    if(value > first[middle]){
        binary_search_mine(middle+1,max,value);
    }
    else if(value < first[middle]){
        binary_search_mine(min,middle-1,value);
    }
    else{
        cnt++;
        if(first[middle + 1] == value){
            binary_search_mine(middle+1,max,value);
        }
        else if(first[middle - 1] == value){
            binary_search_mine(min,middle-1,value);
        }
    }
}

이번에는 조건을 넣어주었습니다. 만약 숫자를 찾게된다면 그 숫자의 앞뒤를 비교하여 순서대로 숫자가 존재할테니 찾을 수 있지 않을까? 생각을 했었습니다. 하지만 이분 탐색은 중간값을 찾아내기 때문에 만약 3개의 동일한 숫자가 있고 숫자의 중간 숫자를 찾아내게 된다면 결국 양쪽으로 찾아야하니 이 방식도 틀린 방식이 되었습니다.

결국 정 답답해서 질문 검색을 해보니 upper_bound, lower_bound로 푸는 문제라고 해서 한 번 찾아보았습니다. 다행히 C++에서는 STL이 존재해서 그대로 풀면 되었습니다.

질문 검색에 한 분이 링크를 올려주셔서

이진탐색-상/하한선((lower bound,upper bound)

주어진 자료에서 중복되지 않은 값이 주어질 때 그 데이터내에 특정 값이 존재하는지 검색하는 방법 중  이진탐색(Binary Search)은 자료를 정렬한후 분할정복방식으로 데이터를 2/1씩 나누면서 값이 존재하는지..

jackpot53.tistory.com

이 글을 토대로 간단하게 설명을 하자면 upper bound는 앞에서 lower bound는 뒤에서 원하는 수의 인덱스를 출력해주는 함수입니다.

자바에서는 이 기능이 없어서 따로 만들어야 한다고 하지만 C++에는 일단 STL이 존재하니 활용하기로 하였습니다.

lower bound(시작, 끝, 찾는 수)

upper bound(시작, 끝, 찾는 수)

의 구조로 형태 자체는 binary_search랑 똑같은 구조입니다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(void){

    long n, m;
    vector<long> first;
    long cnt = 0;

    scanf("%ld", &n);
    for(int i = 0 ; i < n ; i++){
        long temp;
        scanf("%ld", &temp);
        first.push_back(temp);
    }
    sort(first.begin(), first.end());

    scanf("%ld", &m);
    for(int i = 0 ; i < m ; i++){
        long temp;
        scanf("%ld", &temp);
        vector<long>::iterator lower = lower_bound(first.begin(), first.end(), temp);
        vector<long>::iterator upper = upper_bound(first.begin(), first.end(), temp);
        printf("%d ", upper - lower);
    }
}

확실히 STL을 사용하니 코드가 깔끔해진걸 볼 수 있습니다.

자료구조<자료형>::iterator 변수 = lower_bound(배열.시작, 배열.끝, 찾는 수)를 기억하고 가야겠습니다.