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

풀이 시간: 44m33s83

시간 복잡도: O(N)

공간 복잡도: O(N)

참고 자료: https://bbeomgeun.tistory.com/18

문제

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

문제 풀이

처음에는 이분 탐색으로 풀었는데 답이 계속 틀리다고 나왔다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N, M;
    vector<int> sang, num, sortNum; // 상근 카드, 숫자 카드, 정렬된 숫자 카드

    // 입력 및 초기화
    cin >> N; 
    sang = vector<int>(N);
    for (int i = 0; i < N; ++i) 
        cin >> sang[i];

    cin >> M; 
    num = vector<int>(M);
    for (int i = 0; i < M; ++i) 
        cin >> num[i];

    // 오름차순 정렬
    sortNum = num;
    sort(sortNum.begin(), sortNum.end());

    // 카운트 배열 초기화
    vector<int> cnt(M, 0);

    // 이분 탐색
    int sortNumSize = sortNum.size();
    for (int i = 0; i < N; ++i) {
        int left = 0, right = sortNumSize - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (sang[i] < sortNum[mid]) right = mid - 1;
            else if (sang[i] > sortNum[mid])  left = mid + 1;
            else {
                cnt[mid]++;
                break;
            }
        }
    }

    // 출력
    for (int i = 0; i < M; ++i) {
        int index = lower_bound(sortNum.begin(), sortNum.end(), num[i]) - sortNum.begin();
        cout << cnt[index];
		if (i < M - 1) cout << " ";
    }

    return 0;
}

 

다른 코드들을 참고해보니 위 코드는 괜히 꼬아서 구현한 것 같았다. 그 과정에서 발생하는 예외 출력도 분명히 있었기에 틀린 코드로 결과가 나온 것이다.

 

당연히 나는 이분탐색으로 전부 탐색한 후 다시 출력하면 되는 줄 알았는데 그게 아니었다.

그냥 처음 for문 돌려서 입력값을 받을 때, 해당 반복문에서 같이 처리를 해주면 되는 것이었다.

 

https://bbeomgeun.tistory.com/18

위 블로그를 참고하여 코드를 수정해보았다.

 

먼저, 해시 맵의 경우에는 unordered_map을 사용하여 해당 카드의 숫자 num과 해당 숫자인 num의 개수를 저장해준다.

해당 num을 입력받을 때마다 해시 맵에서 해당 num에 대한 개수를 +1 해준다. 그리고 출력해주면 된다.

전체 코드(HashMap)

// 풀이 시간: 44m33s83
// 시간 복잡도: O(N)
// 공간 복잡도: O(N)
#include <iostream>
#include <unordered_map>
using namespace std;

int N, M;
unordered_map<int, int> m; // 카드 숫자 num, 해당 숫자 num의 개수

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; ++i) { // 개수 카운트
		int num; cin >> num;
		m[num]++;
	}
	cin >> M;
	for (int i = 0; i < M; ++i) { // 바로 출력
		int num; cin >> num;
		cout << m[num] << " ";
	}
    return 0;
}

 

하지만 더 시간복잡도가 덜 걸리는 이분 탐색 알고리즘을 사용한 방법이 있다.

 

먼저, 숫자 카드의 각 숫자들을 arr 배열에 인덱스 순서대로 하나씩 대입한다.

그리고 이분탐색을 위해 arr 배열을 정렬한다.

마지막으로 출력해주면 되는데 이때 사용되는 함수는 다음과 같다.

upper_bound(검사 시작 부분, 검사 끝 부분, num): 숫자 num 초과하는 값이 처음 나오는 위치

lower_bound(검사 시작 부분, 검사 끝 부분, num): 숫자 num 이상의 값이 처음 나오는 위치

 

본 문제에 대입하자면 다음과 같이 된다.

만약 arr 배열이 다음과 같다고 치자. 이때 N은 arr 배열의 크기를 의미한다.

arr = [6, 3, 2, 10, 10, 10, -10, -10, 7, 3];

 

upper_bound(arr, arr + N, 10): 3 (숫자 10이 처음 나타나는 위치 인덱스)

lower_bound(arr, arr + N, 10): 6 (마지막으로 나오는 숫자 10의 그 다음 위치 인덱스)

 

이렇게 할 수 있는 이유는 arr 배열이 오름차순으로 정렬되어 있기 때문이고, 숫자 10이 처음 시작하는 위치와 숫자 10이 마지막으로 나오는 위치의 다음 위치의 차이를 구해주면 숫자 10의 개수를 구할 수 있다.

upper_bound(arr, arr + N, num) - lower_bound(arr, arr + N, num)

 

여기서 말하는 arr과 arr + N은 포인터로 해석이 되는데, arr은 arr 배열의 첫 번째 요소를 가리키는 포인터이고, arr + N은 arr 배열의 N번째 요소 다음을 가리키는 포인터가 된다.

전체 코드(이분 탐색)

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

int arr[500002];
int N, M;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; ++i) {
		int num; cin >> num;
		arr[i] = num;
	}
    
	sort(arr, arr + N);

	cin >> M;
	for (int i = 0; i < M; ++i) {
		int num; cin >> num;
		cout << upper_bound(arr, arr + N, num) - lower_bound(arr, arr + N, num) << " ";
	}
}

 

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

10816번: 숫자 카드 2