[Algorithm] [Python] 백준/BOJ - 10015 _ 숫자 카드

10815 - 숫자 카드

---

INDEX

---

1.문제 설명

2.입력

3.출력

4.제출 코드

5.코드 설명

문제 설명

---

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

제출 코드

---

1차 제출 코드

from sys import stdin

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
cmp_arr = list(map(int, stdin.readline().split()))
result = ''
for i in range(m):
    if cmp_arr[i] in arr:
        result += '1 '
    else:
        result += '0 '

print(result)

처음에 제출한 코드는 위와 같다.

배열(arr, cmp_arr) 입력받고 cmp_arr배열 인덱스를 통해 순회하며 원소가 arr 배열 내 같은 원소가 있는지 확인하여 분기하였다.

위 코드는 테스트케이스는 정상적으로 만족하지만 시간초과가 떳다.

이후 문제를 다시 살펴보았다.

상근이는 150만개의 카드를 가질 수 있으며 비교해야 할 카드도 150만개다.

따라서, 단순히 비교해도 약 250000000000번의 연산이 필요하다.

파이썬은 1초에 1000만 ~ 1억번의 연산이 가능하다. 위 계산대로라면 최소 250초가 걸린다..

시간 제한이 2초이므로 효율적 알고리즘을 찾아야 한다.

2차 제출 코드

from sys import stdin
'''
    숫자 카드 N개 가지고 있음.
    정수 M개가 주어졌을 때 이 수가 있는 수인지 아닌지 구해라.
'''

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
arr.sort()                           # 이진 탐색을 위한 정렬

for key in list(map(int, stdin.readline().split())):
    left = 0
    right = n-1

    while True:
        if left > right:
            print(0, end=' ')
            break
        mid = (left + right) // 2
        if arr[mid] == key:
            print(1, end=' ')
            break
        elif arr[mid] > key:
            right = mid - 1
        else:
            left = mid + 1

두번째 제출한 코드는 시간복잡도를 고려한 효율적 탐색을 위해 이진 탐색을 이용하였다. 그 결과 정답으로 처리되었다.

문제풀이

---

이번 문제는 시간복잡도를 고려하여 풀어야하는 문제다.

입력값 N과 M은 1 <= N,M<= 500,000 의 범위를 갖는다. 따라서 비교횟수는 1~250,000,000,000번의 범위를 갖는다.

파이썬은 1초에 약 1000만 ~ 1억번의 연산이 가능하므로 최소 250초 최대 2500초의 시간이 소요된다.

따라서, 보다 효율적으로 탐색할 수 있는 알고리즘이 필요하다.

필자는 이진탐색 알고리즘을 활용하여 문제를 풀었다.

제출 코드에서 이진탐색 부분을 살펴보도록 한다.

while True:
    if left > right:                # left값이 right보다 큰 경우
        print(0, end=' ')
        break
    mid = (left + right) // 2       # mid값 설정
    if arr[mid] == key:             # 비교 배열에서 뽑은 원소가 현재 배열의 중간값과 동일한 경우
        print(1, end=' ')
        break
    elif arr[mid] > key:            # 중간값이 찾고자 하는 값보다 큰 경우 , right 값을 변경하여 범위 수정
        right = mid - 1
    else:
        left = mid + 1              # 중간값이 찾고자 하는 값보다 작은 경우, left 값을 변경하여 범위 수정