[백준(python)] 10815번 : 숫자 카드

[Silver V] 숫자 카드 - 10815

문제 링크

분류

이분 탐색(binary_search), 자료 구조(data_structures), 정렬(sorting)

1. 풀이 방법(실패)

처음에는 알고리즘 생각 없이 그냥 구현했다.
in 연산자를 이용하여 리스트안에 있는지를 찾아보도록 했는데 시간초과가 났다.

# 리스트 탐색 -> 시간초과
N = int(input())
has_card = list(map(int,input().split(' ')))
has_card.sort()

M = int(input())
has_not_card = list(map(int,input().split()))


result= []
for i in has_not_card:
    if i in has_card:
        result.append(1)

    else:
        result.append(0)
print(*result)

그래서 시간을 줄이는 방법을 찾아봤는데, 이 문제는 "이분탐색"을 이용하는 것이었다.

이분탐색이란?

이진탐색(二進探索)이라고 부르거나 Binary Search Algorithm라고 한다.
오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

설명이 어렵게 되어있지만 예제를 들어보면 매우 쉽다.

문제의 예시처럼 [6, 3, 2, 10, -10] 이라는 배열이있다고 해보자.
이분탐색은 정렬을 먼저 해야하는데, 해당 배열을 정렬하면 [-10, 2, 3, 6, 10]이 된다.
우리는 정렬된 배열에서 10이라는 원소를 찾을 것인데, 10은 중간값인 3을 기준으로 크기 때문에 오른쪽으로 가서 검사를 하면 된다.
작다면? 왼쪽으로 가면 된다.

이런식으로 비교해야 할 리스트를 반으로 나눠서 필요한 부분에서만 탐색을 하도록 만드는 알고리즘이 "이분탐색"이다.

2. 풀이 방법(성공)

내가 구현한 이분탐색 중요 알고리즘은 아래와 같다.

def binary_search(target):
    start = 0
    end = len(has_card)-1
    mid = (start+end)//2

    while (end-start >= 0):
        # 중간값과 같으면 1을 리턴함
        if has_card[mid] == target:
            return 1
        # 중간값보다 크면 오른쪽에 있으므로 중간기준으로 +1
        elif has_card[mid] < target:
            start = mid+1
        # 중간값보다 작으면 왼쪽에 있으므로 중간기준으로 -1
        elif has_card[mid] > target:
            end = mid-1
        # 한번 순회할 때 마다 시작, 끝값이 달라지므로 중간값을 다시 구함
        mid = (start+end) // 2
    # 검색해봐도 없으면 0 리턴
    return 0

1. 리스트 크기만큼만 돌도록 한다
2. 중간값과 찾는 값이 같으면 1을 리턴한다
3. 중간값보다 크면 오른쪽, 작으면 왼쪽으로 다시 탐색한다.
4. 순회할 때마다 중간값은 달라지므로 다시 구한다.
5. 전부 다 돌아봐도 없으면 0을 리턴한다.

전체코드

N = int(input())
has_card = list(map(int,input().split(' ')))
has_card.sort()

M = int(input())
has_not_card = list(map(int,input().split()))

result= []

def binary_search(target):
    # 가지고 있는 카드 기준으로 함
    start = 0
    end = len(has_card)-1
    mid = (start+end)//2

    while (end-start >= 0):
        # 중간값과 같으면 1을 리턴함
        if has_card[mid] == target:
            return 1
        # 중간값보다 크면 오른쪽에 있으므로 중간기준으로 +1
        elif has_card[mid] < target:
            start = mid+1
        # 중간값보다 작으면 왼쪽에 있으므로 중간기준으로 -1
        elif has_card[mid] > target:
            end = mid-1
        # 한번 순회할 때 마다 시작, 끝값이 달라지므로 중간값을 다시 구함
        mid = (start+end) // 2
    # 검색해봐도 없으면 0 리턴
    return 0

for i in has_not_card:
    result.append(binary_search(i))
print(*result)