1920 수 찾기

문제

배열 A, B가 주어지는데
B에 있는 원소들이 A안에 존재하는지 판단하는 문제이다.

Link: 수 찾기

A
[4 1 5 2 3]

B
[1 3 7 9 5]

1 - 존재함, 0 없음

-> 정답: 1 1 0 0 1

코드

n = input()
N = list(map(int, input().split()))
m = input()
M = list(map(int, input().split()))

N.sort()

# M이 N안에 존재하나
for m in M:
    exist = 0
    start = 0
    end = len(N)-1
    # <= 하는 이유 1,4 -> 1,2 -> 2,2 로 진행될때 2,2가 실행안됨
    while (start <= end):
        mid = (start + end)//2
        if (m == N[mid]):
            exist = 1
            break
        elif (m < N[mid]):
            end = mid - 1
        else:
            start = mid+1
    print(exist)

활용된 알고리즘

1. 정렬
2. 이진탐색

해설

배열 A 안에 B에 있는 원소 하나하나의 값이 존재하는지 판별하는 문제이므로 A를 정렬하고, 이진탐색을 통해 빠르게 값을 찾는다.

1. A배열을 정렬한다.
2. start(0), end(len A) 초기값을 주고 start <= end 일경우 검사한다.
3. 중간값 mid를 통해 값이 같으면 1을 출력하고 아닐 경우 값에 따라 start와 end의 값을 조정한다.

❗ 주의 사항 start < end로 값을 설정할 경우, [1, 3, 5, 7] 7를 찾을
때, 끝자리의 값들을 찾지 못할 수 있음
start 0 end 3 : arr[1] => 3 < 7
start 2 end 3 : arr[2] => 5 < 7
start 3 end 3 : 동작종료

Today I Learned

1. 파이썬 list의 내장함수 sort, sorted 의 차이
   -> sort는 list의 원형을 바꿈, sorted는 새로운 리스트를 생성(원본 유지)

2. 파이썬은 c로 만들어져있고, sort()의 구현은 timsort라는 알고리즘을 사용했다.(merge sort + insert sort)

3. timsort는 merge sort를 최적화 한 알고리즘으로 시간복잡도는 (NlogN) 이고, 최악의 경우도 NlogN이 나와 다양한 언어에서 sort를 이 알고리즘을 통해서 구현했다.