<1920> 수 찾기 - 이진탐색

문제

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

 

 

출력

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

 

 

 

풀이

import sys

n = int(sys.stdin.readline().rstrip())
nlist = list(map(int, sys.stdin.readline().rstrip().split()))
nlist.sort()

m = int(sys.stdin.readline().rstrip())
mlist = list(map(int, sys.stdin.readline().rstrip().split()))

for i in range(m):
    left = 0
    right = n - 1
    flag = False

    while left <= right:
        middle = (left + right) // 2
        if mlist[i] == nlist[middle]:
            flag = True
            print(1)
            break
        if mlist[i] < nlist[middle]:
            right = middle - 1
        else:
            left = middle + 1
    if flag is False:
        print(0)

 

처음에 그냥 파이썬 내장 기능 활용해서 냈다가 시간초과로 빠꾸먹음..

사실 아직도 시간복잡도에 대한 개념이 명확하지가 않아서, 이럴 때 어떻게 시간을 줄일지 많이 고뇌...

 

예전에 알고리즘 스터디 할 때, 이진탐색만 잘 활용하면 대부분 끝난다는 얘기를 들은 적이 있다.

이진탐색 너무 오랜만에 봐서 어떻게 하는건지 까먹음...ㅋㅋ ..............

 

사실 내가 느끼기엔, 내가 처음 짠 코드가 더 빨라보이게 느껴지는데

왜 이거만 통과가 되는건지는 잘 모르겠다..  이진탐색이 그만큼 매우매우 빠른 걸까..?

 

이진탐색 + 반복문 한번만 쓰려고 엄청 비틀어 봤는데 안돼서 걍 반복문 두번 돌림 

+ 다른사람들 코드 보면 이진탐색 안하고도 풀었는데, 난 왜 시간초과가 떴는지 의문

 

flag는 진짜.. 온몸비틀기의 흔적... ㅋ ㅋ ㅋ ㅋ 

뭐 풀었으니 됐다만 시원하지가 않네