수 찾기

1920번: 수 찾기

🤔생각해보기

이 문제를 요약하면 다음과 같다.

컨테이너 안에 지정된 값(M)이 존재하는지 검사하라.

 

평소 파이썬을 자주 사용했다면 in 연산자를 사용해볼 법하다. 실제로도 in 만 사용해도 해결할 수 있다.

하지만 이 문제는 이진탐색에 관한 문제이므로 in 연산자를 아는지 묻는 문제는 아닐 것이라 판단하고, 이진탐색에 초점을 맞춰서 문제를 해결하도록 한다.

이진탐색을 하기 위해서는 보통 3가지 인덱스를 활용한다.

• start : 배열의 시작 인덱스
• end : 마지막 인덱스
• middle : 중간 인덱스, 여기서부터 검색을 시작하며 조건문의 기준이 된다.

성공 코드

1. Binary Search - Recursion

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().rstrip().split()))

M = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().rstrip().split()))

A.sort()


def binary_search(v, li):
    if len(li) == 1 and v != li[0]:
        return False

    mid = len(li) // 2

    if v == li[mid]:
        return True

    if v < li[mid]:
        return binary_search(v, li[:mid])
    else:
        return binary_search(v, li[mid:])


for num in nums:
    if binary_search(num, A):
        print(1)
    else:
        print(0)

처음은 재귀함수를 작성해서 풀어보았다.

배열의 중간값을 저장해놓고 조건에 따라서 binary_search 함수를 반복해서 호출한다.

재귀를 사용해서 해결하는 방식은 직관적이라 이해하기 좋을 때도 있지만 성능적으로는 대부분 좋지 못한 것 같다.

7732ms 라는 비교적 긴 시간이 걸린다.

2. Binary Search - Standard

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().rstrip().split()))

M = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().rstrip().split()))

A.sort()


def binary_search(v, li):
    start = 0
    end = len(li) - 1

    while start <= end:
        mid = (start + end) // 2
        if li[mid] == v:
            return True
        elif li[mid] < v:
            start = mid + 1
        else:
            end = mid - 1

    return False


for num in nums:
    print(1 if binary_search(num, A) else 0)

워낙 재귀가 성능이 안좋으니 그냥 정석적인 풀이를 다시 작성했다.

292ms 로 빠르게 해결된다.

3. 'in' operator

import sys

N = int(sys.stdin.readline())
A = set(map(int, sys.stdin.readline().rstrip().split()))  # list -> set

M = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().rstrip().split()))

for num in nums:
    print(1 if num in A else 0)

파이썬에 있는 in 연산자를 활용하면 이진탐색 코드를 짤 필요도 없다.

어이없을 정도로 너무나 쉽게 해결이 가능하다... 심지어 232ms 로 가장 빠르기까지 하다!

시간복잡도에 관한 문제를 최소화하기 위해서 list 를 사용하지 않고 set 으로 변환해서 사용한다. 어떤 시간복잡도를 가지고 있는지 궁금하신 분은 첨부한 링크를 참고해보시길 바란다.

Result

 

Reference

TimeComplexity - Python Wiki

Complexity of *in* operator in Python