백준 파이썬 1920번: 수 찾기

www.acmicpc.net/problem/1920

1920번: 수 찾기

문제 유형: 이분 탐색

 

# Solution 1 -  시간 초과

n = int(input())
a = list(map(int, input().split(' ')))
k = int(input())
b = list(map(int, input().split(' ')))

arr = []

for i in range(k):
    if b[i] in a:
        arr.append(1)
    else:
        arr.append(0)
        
for item in arr:
    print(item, end='\n')

일단 당장 생각나는 대로 풀었다. 쓸모없는 어레이를 생성한 후 결과 값을 넣어주고, 마지막에 다시 어레이의 각 요소를 출력하는 방식이다 보니 당연히 시간 초과가 나왔다.

 

# Solution 2

n = int(input())
a = set(map(int, input().split()))
k = int(input())
b = list(map(int, input().split()))

for i in b:
    if i in a:
        print('1')
    else:
        print('0')

개선된 풀이법. Solution 1에서 추가적인 어레이를 생성하지 않고 결과 값만 바로 프린트해주어도 괜찮을 것 같긴 하지만, 여기선 set() 함수도 함께 사용했다.

 

set()은 집합 자료형으로 변환해주는 함수이고 중복을 허용하지 않는 특성을 가지고 있다. 위에서도 unique한 값만을 남기고 중복된 값은 제거하여 시간을 조금이나마 줄이려고 했다.

 

# Solution 3

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
a.sort()

for i in b:
    low, high = 0, n
    while low <= high:
        mid = (low + high) // 2
        if mid < n and mid > -1:
            if a[mid] < i:
                low = mid + 1
            else:
                high = mid - 1
        else: break
    if mid < n and mid > -1:
        if i == a[high + 1]: 
            print(1)
        else: 
            print(0)
    else:
        print(0)

이분탐색을 이용해서 푸는 방법도 있다.

 

 

아래부터 각각 Solution 1, Solution 2, Solution 3로 풀었을 때의 결과.