수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력1

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

예제 출력1

1
1
0
0
1

문제 풀이

시간 초과한 풀이

n=int(input())
lst_n=list(map(int,input().split()))
m=int(input())
lst_m=list(map(int,input().split()))

for mm in lst_m:
    left=min(lst_n)
    right=max(lst_n)
    while left<=right:
        mid=(left+right)//2
        if mm<=mid:
            right=mid-1
            answer=mid
        else:
            left=mid+1
    if answer==mm:
        print(1)
    else:
        print(0)

틀렸던 이유

• 이분탐색은 정렬이 되어있다는 전제하에 이루어진다.
• 처음 코드는 정렬도 되어있지 않은 상태였고, 입력으로 주어지는 리스트lst_n에서 탐색한 것이 아니라 lst_n의 최소값과 최대값 사이의 모든 정수들 중에서 탐색을 했기때문에 시간초과가 일어날 수 밖에 없었다.
  
  

성공한 풀이

n=int(input())
lst_n=list(map(int,input().split()))
m=int(input())
lst_m=list(map(int,input().split()))

lst_n.sort()

for mm in lst_m:
    left=0
    right=len(lst_n)
    if mm<lst_n[left]:
        print(0)
        continue
    elif mm>lst_n[right-1]:
        print(0)
        continue
    while left<=right:
        mid=(left+right)//2
        if mm==lst_n[mid]:
            break
        elif mm<lst_n[mid]:
            right=mid-1
        else:
            left=mid+1
    if lst_n[mid]!=mm:
        print(0)
    else:
        print(1)

1. 정렬을 먼저 해주고
2. 입력으로 주어지는 리스트 값들에서만 탐색을 하도록 mid값을 인덱스로 이용한다.
3. lst_n에 있는 최소값과 최대값보다 작거나 크면 처음부터 걸러주는 작업을 해준다. -> if문 이용
4. while문을 빠져나온 후에 mid 인덱스에 해당하는 리스트 값이 탐색하려는 값과 같으면 1을 출력하고 아니면 0을 출력한다.

다른 사람 풀이

def binary(l, N, start, end):
    if start > end:
        return 0
    m = (start+end)//2
    if l == N[m]:
        return 1
    elif l < N[m]:
        return binary(l, N, start, m-1)
    else:
        return binary(l, N, m+1, end)

위 코드처럼 재귀함수를 이용하여 이분탐색을 할 수도 있다.

추가로 알아본 정보

다른 사람의 풀이를 서칭하다가 in을 이용해서 문제를 푼 코드를 봤다.
의문이 들어서 in을 이용하여 코드를 작성했더니 통과했다. 리스트로 이용해서 in 연산자를 쓰면 시간초과가 발생하고, set으로 변환해준 다음에 in 연산자를 쓰면 시간초과가 발생하지 않고 통과한다!

n=int(input())
lst_n=list(map(int,input().split()))
lst_n=set(lst_n)
m=int(input())
lst_m=list(map(int,input().split()))

for mm in lst_m:
    if mm in lst_n:
        print(1)
    else:
        print(0)

list에서 in 연산자의 시간복잡도는 O(n)이고
set에서 in 연산자의 시간복잡도는 평균 O(1), 최악의 경우 O(n)이기 때문에 set을 이용하여 이 문제를 풀 수 있었다.

in 연산자를 사용할때 set으로 변환한 후 사용하면 시간복잡도를 줄일 수 있을 것 같다.
이분탐색을 이해하기 위해 풀었던 문제이기 때문에 이분탐색 알고리즘으로 풀었지만 또 하나의 지식을 하나 얻어간다.

참고 https://wiki.python.org/moin/TimeComplexity