백준 알고리즘: 1920번 수 찾기 (Python)

문제 정보

---

1920번: 수 찾기

 

핵심

---

단순 탐색 문제이나, 두개의 배열의 길이가 100,000으로 제한되어 있음

만일 순차 탐색으로 이 문제를 풀 경우 최대 100,000^2 번의 탐색이 필요할 수 있으므로 비효율적임

따라서 이진 탐색(Binary Search) 알고리즘을 활용하여 문제를 풀이함

 

풀이

---

# 수 찾기

N = int(input())
A = list(map(int, input().split()))

A.sort()

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

answer = []

def binary(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary(array, target, start, mid - 1)
    else:
        return binary(array, target, mid + 1, end)

for i in range(M):
    num = binary(A, B[i], 0, N-1)
    if num is not None:
        answer.append(1)
    else:
        answer.append(0)

for num in answer:
    print(num)

 

고찰

---

처음 순차 탐색을 활용하여 문제를 풀었을 때 시간 초과가 났음 - 더욱 효율적인 방식으로 문제를 풀어야겠다 생각

이진 탐색의 알고리즘은 알고 있지만, 구현하는 데에 있어 살짝 어려움을 느낌 - 더 많이 활용해보기

리스트에 있는 문자들을 정수로 바꾸어주는 방법을 배움

A = list(map(int, input().split()))

 

 

파이썬에서의 None이라는 별도의 데이터타입에 대하여 배움

if num is not None:

 

또한, 추가로 알게 된 사실인데 이분탐색을 구현해놓은 라이브러리인 bisect 가 존재하여 이를 활용하여 문제를 풀이하면 됨

# 수 찾기
from bisect import bisect_left, bisect_right

N = int(input())
A = list(map(int, input().split()))

A.sort()

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

answer = []

def nums_in_array(array, target):
    return bisect_right(array, target) - bisect_left(array, target)

for i in range(M):
    if nums_in_array(A, B[i]) > 0:
        answer.append(1)
    else:
        answer.append(0)

for num in answer:
    print(num)

 

여기서 bisect_right와 bisect_left는 해당 배열에서 target이 array에 삽입할 오른쪽, 왼쪽 index를 의미한다

# 예를 들어 배열이 1 2 3 4 5 가 있을 때
# bisect_left(array, 3) 과 bisect_right(array, 3) 을 해보면

A = [1, 2, 3, 4, 5]
print(bisect_left(A, 3))
print(bisect_right(A, 3))

# bisect_left(A, 3) -> 2
# bisect_right(A, 3) -> 3
# 이 출력되는 것을 알 수 있다

 

따라서 해당 방식을 활용하면 bisect_right - bisect_left 는 해당 배열에서의 target 정수가 몇 개 들어있는 지 알수 있으므로

이를 통해 1개 이상 들어있는 수라면 1을 출력하고, 그렇지 않다면 0을 출력하는 방식으로 문제를 해결할 수 있을 것이다