백준 10815번 숫자 카드 Python

---

백준 10815번 숫자 카드 Python

---

문제 설명

문제

숫자 카드는 정수 하나가 적혀 있는 카드입니다. 상근이는 숫자 카드 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을 밑줄로 강조한 상태입니다.

질문 목록    : _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)$ 수준에 그칩니다.
• 완전탐색보다 훨씬 빠르고 효율적입니다.

---

✅ 전체 코드 (Python)

N=int(input())
arr1=list(map(int,input().split()))
M=int(input())
arr2=list(map(int,input().split()))

arr1.sort() # 이진 탐색을 위해 정렬

for i in arr2:
    left=0
    right=N-1
    while True:
        if(left>right): # left가 right보다 커지면 숫자가 없다는 의미
            print(0,end=' ')
            break
        mid=(left+right)//2 # 중간 인덱스 계산 (Python의 //는 정수 나눗셈)

        if(arr1[mid]==i): # 숫자를 찾은 경우
            print(1,end=' ')
            break

        if arr1[mid]>i: # 중간 값이 찾는 값보다 크면, 오른쪽 절반을 버리고 왼쪽 탐색
            right=mid-1
        else: # 중간 값이 찾는 값보다 작으면, 왼쪽 절반을 버리고 오른쪽 탐색
            left=mid+1

---

🔍 코드 분해 및 설명

📌 [1] 입력 및 리스트 생성

N=int(input())
arr1=list(map(int,input().split()))
M=int(input())
arr2=list(map(int,input().split()))

• `N`과 `M`은 각각 상근이의 카드 개수와 찾아야 할 숫자의 개수입니다.
• `arr1`은 상근이가 가진 숫자 카드들을 저장하는 리스트입니다. `map(int,input().split())`을 사용하여 공백으로 구분된 문자열 입력을 정수형 리스트로 변환합니다.
• `arr2`는 찾아야 할 숫자들을 저장하는 리스트입니다.

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

arr1.sort() # 이진 탐색을 위해 정렬

• **이진 탐색은 반드시 정렬된 데이터에 대해서만 동작**하므로, `arr1` 리스트를 `sort()` 메서드를 사용하여 오름차순으로 정렬합니다.

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

for i in arr2:
    left=0
    right=N-1
    while True:
        if(left>right):
            print(0,end=' ')
            break
        mid=(left+right)//2

        if(arr1[mid]==i):
            print(1,end=' ')
            break

        if arr1[mid]>i:
            right=mid-1
        else:
            left=mid+1

• `arr2`에 있는 각 숫자(`i`)에 대해 이진 탐색을 수행합니다.
• `left`와 `right`는 각각 탐색 범위의 시작과 끝 인덱스를 나타냅니다. 초기에는 `0`과 `N-1`로 설정됩니다.
• `while True` 루프를 통해 이진 탐색을 진행합니다.
• `left > right`가 되면 더 이상 탐색할 범위가 없다는 뜻이므로, 숫자가 없다고 판단하고 `0`을 출력한 후 루프를 종료합니다.
• `mid`는 `left`와 `right`의 중간 인덱스입니다. Python의 `//` 연산자는 정수 나눗셈을 수행하여 소수점 이하를 버립니다.
• `arr1[mid]`가 찾는 숫자 `i`와 같으면, 숫자를 찾은 것이므로 `1`을 출력하고 루프를 종료합니다.
• `arr1[mid]`가 `i`보다 크면, 찾는 숫자는 `mid`의 왼쪽에 있으므로 `right`를 `mid - 1`로 업데이트합니다.
• `arr1[mid]`가 `i`보다 작으면, 찾는 숫자는 `mid`의 오른쪽에 있으므로 `left`를 `mid + 1`로 업데이트합니다.
• `print(0, end=' ')` 또는 `print(1, end=' ')`를 사용하여 결과 값 뒤에 공백을 추가하며 출력합니다.

✅ 결론 정리

• 이 코드는 Python의 리스트와 기본적인 반복문, 조건문을 활용하여 **이진 탐색 알고리즘**을 구현한 것입니다.
• `arr1` 리스트를 사전에 **정렬**하는 것이 이진 탐색의 필수 전제 조건입니다.
• `left`, `right`, `mid` 포인터를 사용하여 탐색 범위를 효율적으로 줄여나가는 방식이 핵심입니다.
• 시간 복잡도는 각 숫자에 대해 $\log_2(N)$이므로, 총 **$M \times \log_2(N)$**이 되어 N과 M이 50만까지인 경우에도 2초의 시간 제한을 충분히 만족합니다.