[Python] 수 찾기 (백준 1920번 파이썬)

수 찾기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

218717

66111

44035

29.713%

문제

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개의 배열 안에 m개의 숫자들이 들어있는지 판단하는 문제입니다.

- 문제 설명이 조금 애매한데, 정확하게는 m개의 배열(두 번째 배열)의 수를 하나씩 꺼내서 n개의 배열(첫번째 배열) 안에 있는지 없는지 판단만 하면 됩니다.

- 이분탐색으로 해결하였으나, 단순히 배열에서 in 을 통해 확인만 해도 괜찮을 것 같습니다.

 

문제 풀이

- 기본적인 이분탐색 방법을 이용하였습니다. 다만, while문의 종료 조건을 True로 두고, left가 right보다 커질 경우에 0 출력 후 종료되게 하였습니다.(결과가 없을 경우 0을 출력하기 위함)

 

코드

n = int(input())
a = list(map(int, input().split())) #반복문 돌 놈
m = int(input())
arr = list(map(int, input().split())) # 있는지 확인할 놈
a.sort()


for i in arr:
    left =0
    right = n-1
    while True:
        mid = (left+right)//2
        if left > right:
            print(0)
            break
        if a[mid] == i:
            print(1)
            break
        elif i> a[mid]:
            left = mid +1
        elif i<a[mid]:
            right = mid - 1

이분탐색 과정은 각 배열의 절반씩 줄여가며 탐색하기 때문에 O(logn)의 시간복잡도를 갖습니다.

따라서 해당 코드의 시간복잡도는 

정렬과정 : O(nlogn)

이분탐색 : O(logn) 입니다.

이에 따라 전체 시간복잡도는 O(nlogn)인데, 이분 탐색 과정의 시간복잡도가 짧더라도, 정렬과정으로 인해 시간적으로 손해를 보게 됩니다.

 

해당 이유만을 살펴보면, 문제 이해에서 언급한대로 단순 선형 탐색으로 in을 통해 검사하는 것이 더 효율적일 것입니다.(입력이 10만이기 때문)

100만, 1000만이 된다고 해도, 애초에 정렬되어 있는 숫자가 아니라면 시간복잡도로 인해 선형탐색이 더 효과적일 것입니다.