[백준] 1920 수 찾기

파이톨치·2022년 8월 8일
0

백준

목록 보기
2/12

코드

시간 초과

# N개의 정수를 입력 받기
n = int(input())

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

# M개의 정수를 입력 받기
m = int(input())

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

# 출력하기
for word in b:
    if word in a:
        print(1)
    else:
        print(0)

시간 초과 이유 : 선형 탐색이 너무 비효율적임.

시간 초과 2

# N개의 정수를 입력 받기
n = int(input())

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

# M개의 정수를 입력 받기
m = int(input())

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

# 정렬하기

a.sort()
b.sort()

# 출력하기
for word in b:
    if word in a:
        print(1)
    else:
        print(0)

시간 초과 이유 2 : 정렬을 하면 탐색시간이 줄어들 것이라 생각했지만 여전히 비효율적임.

올바른 풀이

# N개의 정수를 입력 받기
n = int(input())

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

# M개의 정수를 입력 받기
m = int(input())

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

# 정렬하기
a.sort()

# 탐색하기
def binary_search(a, alpha):
    start = 0
    end   = len(a) - 1

    while end >= start:
        mid   = (start + end) // 2 
        target = a[mid]
        
        if alpha == target:
            return 1
        elif alpha < target:
            end = mid - 1
        elif alpha > target:
            start = mid + 1
    
    return 0

# 출력하기
for alpha in b:
    print(binary_search(a, alpha))

해결 방법 : 이진탐색을 이용해 시간 복잡도를 log(n) 으로 줄임

문제 링크

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

profile
안알랴줌

0개의 댓글