[Python] 백준 1920. 수 찾기

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

1920번: 수 찾기

 

문제설명

[4,1,5,2,3] 입력받은 리스트가 있고 다른 리스트 [1,3,7,9,5] 가 있다고 했을 때

[4, 1, 5, 2, 3] 각각의 숫자들이 두번째 리스트에 들어있는지 확인하는 문제이다.

 

이 문제는 정말 쉽게 풀거라고 생각했다.

n = int(input())
lst = list(map(int, input().split()))

m = int(input())
lst2 = list(map(int, input().split()))

answer = []
for num in lst2:
    if num in lst:
        answer.append(1)
    else:
        answer.append(0)

for c in answer:
    print(c)

찾아야 될 숫자 in 두번째리스트 입력하면 손쉽게 찾을 수 있지 않을까? 했지만 내가 만난 오답은 시간초과!!

 

고민하던 중 문제 밑 알고리즘 분류로 '이분탐색' 이 적혀있었다.

 

이분탐색으로 풀어보자

 

이분탐색을 풀기위해 start, end , mid 을 포인터로 지정할 것이다.

• start, end, mid 지점에 내가 찾는 target 가 있다면 flag = 1 로 바꿔 반복문이 끝나면 answer 배열에 저장을 해주려고 한다.
• target이 mid이랑 비교했을때 크다면 start의 위치를 mid로 옮겨 찾을 범위를 좁혀준다.
• target이 mid 보다 작다면 end의 위치를 end로 옮겨 찾을 범위를 좁혀준다.

 

start , end, mid 지점에서 바로 target을 찾았을때 찾았다는 flag =1 과 반복문을 탈출한다.

if target == lst[start] or target == lst[end-1] or target == lst[mid]:
            flag = 1
            break

 

target이 작거나 크면 start와 end의 위치를 바꿔주는 조건문을 걸어준다.

elif target > lst[mid]:
            start = mid
else:
    end = mid

 

하지만 여기서 끝내면 만약 target이 리스트안에 없으면 무한루프에 빠지게 된다.

그 부분을 해결하기 위해 찾아낸 방법은 end-start =1 이면 모든 숫자를 다 확인했기 때문에 탈출을 하도록 했다.

if end-start == 1:
            break

 

전체코드

n = int(input())
lst = list(map(int, input().split()))

lst.sort()

m = int(input())
lst2 = list(map(int, input().split()))


answer = []
for target in lst2:
    flag = 0
    start = 0
    end = len(lst)
    while start < end:
        mid = (start + end) // 2
        if target == lst[start] or target == lst[end-1] or target == lst[mid]:
            flag = 1
            break
        elif target > lst[mid]:
            start = mid
        else:
            end = mid

        if end-start == 1:
            break
    answer.append(flag)

for i in answer:
    print(i)