BOJ 10816 - 숫자 카드 2 문제풀이

문제를 읽고 이해하기

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

재정의와 추상화

입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드가 몇 개인지 출력하는게 문제이다. 이 문제를 처음에는 map을 이용해 문제를 풀었다.

map을 이용한 풀이

map은 삽입, 삭제, 접근 모두 시간 복잡도가 logn이므로 모든 M개의 수에 대해서 검사하는 시간은 O(MlogN)이다. N이 500000이고, M이 500000이라고 했을 때, 1억보다 작으므로 1초보다 적은 시간이 걸린다고 생각하였다.

알고리즘은 다음과 같다. 카드에 적혀있는 숫자 int형 key와 그 숫자에 대한 개수를 저장하는 int형 value를 가지는 map<int, int>형 변수를 선언한다. 그리고 처음 N개의 수를 받을 때, map[카드에 적혀있는 숫자]++;를 통해 개수를 증가시킨다.

그리고 M개의 수를 받을 때, 수를 받을 때마다 map[찾을 숫자]를 통해 개수를 출력하게 하였다. 코드는 아래와 같다.

#include <iostream>
#include <map>
using namespace std;

map<int, int> cards;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n;
    while (n--) {
        int num;
        cin >> num;
        cards[num]++;
    }
    cin >> m;
    while (m--) {
        int num;
        cin >> num;
        cout << cards[num] << ' ';
    }

    return 0;
}

그러나, map을 이용한 풀이는 이 문제의 의도가 아니므로 그냥 이런 방법이 있다 정도로만 알고 있자.

upper_bound와 lower_bound를 이용한 풀이

2020/04/03 - [언어/C, C++] - [C++ STL] upper_bound, lower_bound 알아보기

[C++ STL] upper_bound, lower_bound 알아보기

upper_bound와 lower_bound 모두 logn의 시간 복잡도로 값을 얻을 수 있다. 따라서 총 O(MlogN)의 시간이 걸린다. 처음 N개의 수를 vector를 이용해 저장하고, 그 수를 오름차순으로 정렬한다. 그리고 다음 M개의 수에 대해 아래와 같은 코드를 적용한다.

cout << upper_bound(cards.begin(), cards.end(), num) - lower_bound(cards.begin(), cards.end(), num) << ' ';

(upper_bound와 lower_bound에 대해 이미 알고 있다는 전제 하에 설명하겠습니다.)

아래 예시를 보자.

정렬된 N개의 수가 1, 1, 2, 3, 4, 5, 6, 9 일 때, 우리가 1의 개수를 알고 싶다고 하자.

upper_bound(begin, end, 1)를 하면 세 번째 원소를 가리키는 이터레이터가 반환된다. 그 이유는 upper_bound는 정렬된 배열에서 찾고자 하는 수보다 큰 수 중에서 처음으로 찾은 수를 가리키는 이터레이터를 반환하는 함수이기 때문이다.

lower_bound(begin, end, 1)를 하면 첫 번째 원소를 가리키는 이터레이터가 반환된다. 그 이유는 lower_bound는 정렬된 배열에서 찾고자 하는 수보다 작지 않은 값(이상의 값) 중에서 처음으로 찾은 수를 가리키는 이터레이터를 반환하는 함수이기 때문이다.

따라서, (upper_bound 반환 값 - lower_bound 반환 값)을 하면 (3번째를 가리키는 이터레이터 - 1번째를 가리키는 이터레이터)이므로 찾고자 하는 수인 1의 개수를 얻을 수 있다.

이러한 upper_bound와 lower_bound의 원리를 이용하여 찾고자 하는 수의 개수를 얻을 수 있다.

코드 작성

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> cards;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n;
    while (n--) {
        int num;
        cin >> num;
        cards.push_back(num);
    }
    sort(cards.begin(), cards.end());
    cin >> m;
    while (m--) {
        int num;
        cin >> num;
        cout << upper_bound(cards.begin(), cards.end(), num) - lower_bound(cards.begin(), cards.end(), num) << ' ';
    }

    return 0;
}