백준 10815 숫자 카드 C++

---

백준 10815번 숫자 카드 C++

---

문제 설명

문제

숫자 카드는 정수 하나가 적혀 있는 카드입니다. 상근이는 숫자 카드 N개를 가지고 있습니다. 그 후 정수 M개가 주어졌을 때, 이 수가 상근이가 가지고 있는 숫자 카드인지 아닌지를 각각 확인하는 프로그램을 작성하십시오.

• 숫자 카드에 같은 수가 적혀 있는 경우는 없습니다.
• 숫자 카드에 적힌 수와 확인할 수는 -10,000,000 이상, 10,000,000 이하의 정수입니다.
• N, M은 각각 500,000 이하의 자연수입니다.
• 시간 제한은 2초입니다.

테스트케이스

입력
5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

출력
1 0 0 1 1 0 0 1

문제 해설

입력값 기준으로 상근이가 가진 카드 목록은 다음과 같습니다.

6 3 2 10 -10

질문자는 상근이에게 다음과 같이 8개의 숫자를 차례대로 불러줍니다.

10 9 -5 2 3 4 5 -10

상근이는 각 숫자에 대해 본인의 카드 목록에 해당 숫자가 있는지 찾고, 있으면 `1`, 없으면 `0`을 출력합니다.

---

첫 번째 숫자: 10

질문 목록    : _10_  9  -5  2  3  4  5  -10
상근이 카드  : 6  3  2  _10_  -10

질문 목록의 첫 번째 숫자인 10은 상근이 카드 네 번째 위치에서 찾을 수 있으므로 출력값은 `1`입니다.

두 번째 숫자: 9

질문 목록    : 10  _9_  -5  2  3  4  5  -10
상근이 카드  : 6  3  2  10  -10

질문 목록 두 번째 숫자인 9는 상근이 카드 어디에서도 찾을 수 없습니다. 따라서 출력값은 `0`입니다.

이러한 방식으로 남은 숫자들도 하나씩 차례대로 상근이 카드에 존재하는지 확인하고, 각 숫자마다 `1` 또는 `0`을 출력합니다.

최종 출력은 아래와 같습니다.

1 0 0 1 1 0 0 1

---

아이디어

1. 이진 탐색을 사용합니다.

이 문제는 상근이가 가진 숫자 카드들(N개) 중에서, 특정 숫자(M개)가 존재하는지 빠르게 확인해야 합니다.

브루트포스(완전탐색)를 사용하면 시간 초과가 발생하므로, 탐색 대상인 상근이 카드 배열을 정렬한 뒤, 각 숫자에 대해 **이진 탐색(binary search)**을 수행하면 됩니다.

---

2. 브루트포스를 사용하면 O(N × M)입니다.

상근이 카드

6 3 2 10 -10

찾아야 할 숫자들

10 9 -5 2 3 4 5 -10

숫자 1: 10을 찾는 과정

상근이 카드: [6] 3 2 10 -10
찾는 숫자:   10

상근이 카드: 6 [3] 2 10 -10
찾는 숫자:   10

상근이 카드: 6 3 [2] 10 -10
찾는 숫자:   10

상근이 카드: 6 3 2 [10] -10
찾는 숫자:   10  → 찾음

숫자 2: 9를 찾는 과정

상근이 카드: [6] 3 2 10 -10
찾는 숫자:   9

상근이 카드: 6 [3] 2 10 -10
찾는 숫자:   9

상근이 카드: 6 3 [2] 10 -10
찾는 숫자:   9

상근이 카드: 6 3 2 [10] -10
찾는 숫자:   9

상근이 카드: 6 3 2 10 [-10]
찾는 숫자:   9  → 못 찾음

정리

• 숫자 하나를 찾기 위해 상근이 카드 전체를 최대 5번 비교
• 이를 찾아야 할 숫자 8개에 대해 반복 → 40번 비교
• 숫자가 많아질수록 비교 횟수는 기하급수적으로 증가 → 시간 초과 발생

---

3. 이진 탐색을 사용합니다.

📌 이진 탐색(Binary Search) 개념 요약

• 이진 탐색은 정렬된 배열에서 특정 값을 매우 빠르게 찾는 알고리즘입니다.
• 탐색할 때마다 전체 범위를 반으로 나누어 좁혀 가면서 원하는 값을 찾습니다.
• 배열의 크기가 N일 때, $\log_2(N)$ 번의 비교만으로도 값을 찾거나 찾을 수 없음을 판별할 수 있습니다.
• 숫자를 M개 찾아야 한다면, 전체 시간 복잡도는 $M \times \log_2(N)$ 입니다.

예시:

• 상근이 카드가 50만 장(N = 500,000)이고,
• 질문 숫자가 8개(M = 8)일 경우
  → 최악의 경우라도 약 $8 \times 20 = 160$번의 비교면 충분합니다.
• 완전 탐색의 $8 \times 500,000 = 4,000,000$번에 비해 수천 배 빠릅니다.

🔧 전제 조건: 정렬된 상근이 카드 배열

이진 탐색을 쓰기 위해, 먼저 상근이의 숫자 카드 배열을 오름차순으로 정렬합니다. 정렬된 배열과 인덱스는 다음과 같습니다:

value:  -10   2   3   6   10
index:    0    1   2   3    4

• `value`는 카드에 적힌 숫자이고,
• `index`는 배열에서의 위치입니다.
• 아래 탐색 단계에서 나오는 `left`, `mid`, `right`는 모두 이 `index`를 기준으로 움직입니다.

🔍 예제 1: 숫자 10을 찾는 과정

🎯 목표 숫자: 10

1단계

value:  -10   2   3   6   10
index:    0    1   2   3    4
          ↑         ↑     ↑
        left       mid   right
         (0)        (2)    (4)

• `mid`가 가리키는 값은 3
• 10은 3보다 큽니다 → 왼쪽 절반은 버리고 오른쪽만 탐색

→ left = mid + 1 = 3
→ right = 그대로 = 4

2단계

value:  -10   2   3   6   10
index:    0    1   2   3    4
                          ↑ ↑
                        left right
                          ↑
                         mid
                         (3)

• `mid`는 인덱스 3, 값은 6
• 10은 6보다 크므로 → 또 오른쪽만 탐색

→ left = mid + 1 = 4
→ right = 그대로 = 4

3단계

value:  -10   2   3   6   10
index:    0    1   2   3    4
                               ↑
                  left/mid/right
                          (4)

• `mid`는 인덱스 4, 값은 10
• 찾는 숫자와 정확히 일치! 🎯 찾음

🔍 예제 2: 숫자 9를 찾는 과정

🎯 목표 숫자: 9

1단계

value:  -10   2   3   6   10
index:    0    1   2   3    4
          ↑         ↑     ↑
        left       mid   right
         (0)        (2)    (4)

• `mid`는 인덱스 2, 값은 3
• 9는 3보다 큼 → 왼쪽 제거, 오른쪽 탐색

→ left = mid + 1 = 3
→ right = 그대로 = 4

2단계

value:  -10   2   3   6   10
index:    0    1   2   3    4
                          ↑ ↑
                        left right
                          ↑
                         mid
                         (3)

• `mid`는 인덱스 3, 값은 6
• 9는 6보다 큼 → 다시 오른쪽만 탐색

→ left = mid + 1 = 4
→ right = 4

3단계

value:  -10   2   3   6   10
index:    0    1   2   3    4
                               ↑
                  left/mid/right
                          (4)

• `mid`는 인덱스 4, 값은 10
• 9는 10보다 작음 → 오른쪽 제거

→ right = mid - 1 = 3
→ left = 4

→ 이제 `left > right` 상태 → 탐색 종료

• 🎯 숫자 9는 배열에 존재하지 않음

✅ 정리: 왜 이진 탐색은 빠른가?

• 탐색 범위를 매번 절반으로 줄이기 때문입니다.
• 예시에서 배열 길이는 5였고, 단 3번의 비교만으로 결과를 얻었습니다.
• 배열 길이가 50만이라도 최대 약 20번의 비교로 충분합니다.
• 찾을 숫자가 M개일 때, 총 비교 횟수는 $M \times \log_2(N)$ 수준에 그칩니다.
• 완전탐색보다 훨씬 빠르고 효율적입니다.

---

✅ 전체 코드 (C++)

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int N,M;
    cin>>N;
    int*arr1 = new int[N];
    for(int i=0;i<N;i++)
        cin>>arr1[i];
    cin>>M;
    int*arr2=new int[M];
    for(int i=0;i<M;i++)
        cin>>arr2[i];
    make_heap(arr1, arr1 + N);
    sort_heap(arr1, arr1 + N);
    
    for(int i=0;i<M;i++)
    {
        int mid;
        int left=0;
        int right=N-1;
        while(true)
        {
            if(left>right)
            {
                cout<<0<<" ";
                break;
            }
            mid=(left+right)/2;
            if(arr1[mid]==arr2[i])
            {
                cout<<1<<" ";
                break;
            }
            if(arr1[mid]<arr2[i])
                left=mid+1;
            else
                right=mid-1;
        }
    }
    
    delete[] arr1;
    delete[] arr2;
    return 0;
}

---

🔍 코드 분해 및 설명

📌 [1] 입력 및 배열 동적 할당

int N, M;
cin >> N;
int* arr1 = new int[N];
for(int i = 0; i < N; i++)
    cin >> arr1[i];

cin >> M;
int* arr2 = new int[M];
for(int i = 0; i < M; i++)
    cin >> arr2[i];

• `arr1`은 상근이가 가지고 있는 숫자 카드 배열입니다 (N개).
• `arr2`는 찾아야 할 숫자들의 목록입니다 (M개).
• 사용자로부터 두 배열의 값을 입력받습니다.
• `new` 키워드를 사용하여 동적 배열 생성 (메모리를 수동으로 할당).

📌 [2] 정렬 (이진 탐색을 위한 준비)

make_heap(arr1, arr1 + N);
sort_heap(arr1, arr1 + N);

• `arr1`을 힙 정렬을 통해 오름차순 정렬합니다.
• 정렬을 해야 이진 탐색(binary search)을 사용할 수 있기 때문입니다.
• 여기서는 `make_heap` → `sort_heap`의 표준 라이브러리 조합을 활용합니다.

📌 [3] 이진 탐색 실행 (M개의 숫자 각각에 대해)

for(int i = 0; i < M; i++)
{
    int mid;
    int left = 0;
    int right = N - 1;
    while(true)
    {
        if(left > right)
        {
            cout << 0 << " ";
            break;
        }
        mid = (left + right) / 2;
        if(arr1[mid] == arr2[i])
        {
            cout << 1 << " ";
            break;
        }
        if(arr1[mid] < arr2[i])
            left = mid + 1;
        else
            right = mid - 1;
    }
}

• `arr2[i]`에 있는 숫자 하나를 `arr1`에서 이진 탐색으로 찾는 과정입니다.
• `left`, `right`, `mid` 포인터를 이용해 탐색 범위를 반으로 줄이면서 확인합니다.
• 숫자를 찾으면 `1`을 출력하고, 없으면 `0`을 출력합니다.
• 이 과정을 M번 반복하여 M개의 숫자에 대한 존재 여부를 모두 출력합니다.

📌 [4] 메모리 해제 및 종료

delete[] arr1;
delete[] arr2;
return 0;

• `new`로 생성한 배열은 수동으로 `delete[]`를 사용해 메모리 해제해야 합니다.
• 프로그램 정상 종료.

---

✅ 결론 정리

• `arr1`은 이진 탐색을 위해 반드시 정렬되어 있어야 합니다. (`make_heap` → `sort_heap`을 통해 정렬 처리)
• 이진 탐색 루프 내부에서는 `left`, `right`, `mid`를 이용하여 탐색 범위를 절반씩 줄이며 찾고자 하는 값을 효율적으로 찾습니다.
• M개의 숫자 각각에 대해 이진 탐색을 수행하므로, 전체 시간 복잡도는 $M \times \log_2(N)$이 됩니다.
• `new`, `delete[]`를 사용한 동적 메모리 관리는 C++에서는 필수적인 습관입니다. 메모리 누수를 방지하고, 안정적인 프로그램 실행을 위해 필요합니다.