2022.02.23 [백준] (python 파이썬) 수 찾기

 

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

1920번: 수 찾기

 

---

풀이

2가지 방법으로 문제를 해결했다.

 

1. 이분 탐색

먼저 이분탐색은 배열이 정렬된 상태에서 가능하기 때문에 arr배열을 정렬 후, 

시작과 끝 인덱스를 first, last로 지정한다. 

시작과 끝의 중간지점을 mid로 지정 후, mid값과 value를 비교한다.

만약 값이 동일하다면 1일 출력해주고,

mid값이 크다면 value와 같은 값은 mid값보다 앞에 있으므로 last를 mid-1로 바꿔준다. 

또는 mid값이 작다면 value와 같은 값은 mid값보다 뒤에 있으므로 first를 mid+1로 바꿔준다.

이렇게 범위를 줄여가면서 해당 값을 찾아준다.

만약 while문이 다끝나도 찾지 못했으면 arr배열에 value값이 없으므로 0을 리턴해준다.

출처 : https://dongdd.tistory.com/50

1. 이분 탐색 코드

n=int(input())
arr=list(map(int,input().split()))
arr.sort()
m=int(input())
arr2=list(map(int,input().split()))
 
def binary_search(arr,value):
    first=0
    last=n-1
 
    while first<=last:
        mid=(first+last)//2
        if arr[mid]==value:
            return 1
        if arr[mid]>value:
            last=mid-1
        else:
            first=mid+1
    return 0
 
 
for i in arr2:
    print(binary_search(arr,i))

2. 집합 자료형

이분탐색을 쓰지 않고도 풀 수 있을거같아 처음에 list를 이용해서 in arr을 통해 포함여부를 판단하여 1 또는 0을 출력했다. 하지만 시간 초과가 발생하였고 시간 복잡도를 알아본 결과 list의 포함여부판단은 O(N)이 걸린다는것을 알게 되었다. 그래서 다른 집합 자료형을 알아보던 중, set을 사용하면 포함여부판단이 O(1)이 걸린다는 것을 알고 set을 이용하여 코드를 작성하였다.

 

탐색과 조회가 주된 목적이면 딕셔너리나 set을 이용하자!!!

https://chancoding.tistory.com/43

[Python] 파이썬 자료형 및 연산자의 시간 복잡도(Big-O) 총 정리

 

2. 자료형 코드

n=int(input())
arr=set(input().split())
m=int(input())
arr2=input().split()
for i in arr2:
    print(1 if i in arr else 0)