[Python] 백준 풀기 1920 - 수 찾기

파이썬 백준 1920번

실버4

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

 

문제 보기

분류: 자료 구조, 정렬, 이분 탐색

 

 

 

문제 풀기

이분 탐색 카테고리의 문제이긴 하나 문제를 보자마자 리스트 안의 원소를 찾는 형식의 코드가 바로 떠올랐다.

하지만, 이분 탐색을 배우기 위한 지금의 시간이니 이분 탐색으로 풀어본다.

 

일단 주어진 N 값들을 sorted() 함수로 오름차순 정렬을 하여 중간 나눌 준비를 한다.

MM_ls 가 매번 for loop 을 돌면서 찾을 대사이 되는 m 을 하나씩 내뱉어 준다. 이때, NN_ls 의 어느 두 수 사이에 위치해 있는지 지속적으로 비교를 하되 그 구간은 절반의 절반의 절반... 으로 빠르게 줄여지는.. 이 이분 탐색의 핵심을 이용한다.

NN_ls 의 탐색 구간을 변수 left 와 right 의 구간으로 가두고 mid = (left + right) // 2 의 mid 값을 지정하여 비교해 간다. 이때, 현재 구간의 중간에 위치한 NN_ls[mid] 값이 찾고자 하는 m 값과 같게 되면 존재하기에 1 을 프린트해주고, 그렇지 않으면 다시 크기 비교를 하여 mid 에 대한 구간을 새로 지정하여 빠르게 찾아 나간다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnBinarySearch(m, NN_ls, left, right):
    if left > right:
        return 0
    
    mid = (left + right) // 2
    
    if m == NN_ls[mid]:
        return 1
    elif m < NN_ls[mid]:
        return fnBinarySearch(m, NN_ls, left, mid - 1)
    elif m > NN_ls[mid]:
        return fnBinarySearch(m, NN_ls, mid + 1, right)


if __name__ == "__main__":
    N = int(inputdata().strip())
    NN_ls = sorted(list(map(int, inputdata().split())))
    M = int(inputdata().strip())
    MM_ls = list(map(int, inputdata().split()))
    
    print(NN_ls)          #
    print(MM_ls)          #

    for m in MM_ls:
        left = 0
        right = len(NN_ls) - 1
        result = fnBinarySearch(m, NN_ls, left, right)
        print(result)



# 5
# 4 1 5 2 3
# 5
# 1 3 7 9 5

# [1, 2, 3, 4, 5]
# [1, 3, 7, 9, 5]
# 1
# 1
# 0
# 0
# 1

 

 

 

추가 하기

if 와 in 을 통해 처음 쉽사리 생각한 방법

import sys
inputdata = sys.stdin.readline

if __name__ == "__main__":
    N = int(inputdata().strip())
    NN_ls = set(map(int, inputdata().split()))          # set() 을 사용하자. sorted(list(...)) 를 사용하는데 주의하자.
    M = int(inputdata().strip())
    MM_ls = list(map(int, inputdata().split()))
    
    print(NN_ls)          #
    print(MM_ls)          #

    for m in MM_ls:
        if m in NN_ls:
            print(1)
        else:
            print(0)



# 5 
# 4 1 5 2 3
# 5
# 1 3 7 9 5

# {1, 2, 3, 4, 5}
# [1, 3, 7, 9, 5]
# 1
# 1
# 0
# 0
# 1

이미 제출한 코드를 간단히 for m in MM_ls: 만 수정하였다가 시간 초과를 받았다.

이리저리 알아보다가 NN_ls 을 입력받는 방법에서 set() 함수를 사용해야 함을 인지하였다. 그래서 혹시 sorted() 함수가 적용되어 시간 복잡도가 올라갔나 생각해서 제거해 보고 list() 만 사용해 보았으나 이 또한 시간 초과를 받게 되었다.

list() 에서의 in 과 set() 에서의 ln 이 다름을 느낄 수 있었는데 이 부분은 좀 더 찾아봐야겠다.

(if _ in list() 와 if _ in set() 의 작동 방식이 궁금하다..)

 

 

이분 탐색 코드를 제출한 맨 아래 결과와 if in list() 를 사용했을 때 시간초과가 난 중간, 그리고 if in set() 을 사용했을때 나타난 결과가 제일 위이다. 답안 제출 시 시간에서 많은 차이를 보인다.