백준 10815 - set, list 시간 복잡도 / 이진 탐색

내 풀이

import math
import sys
input = sys.stdin.readline
N = int(input())
card_num = list(map(int, input().split()))
M = int(input())
card_S = list(map(int, input().split()))

card_num_sort = sorted(card_num)
card_S_sort = sorted(card_S)

result = [0 for i in range(M)]

for i in range(N):
    low = 0
    high = len(card_S)-1
    while low <= high:
        mid = math.floor(low + (high-low) / 2)

        if card_S_sort[mid] == card_num[i]:
            result[card_S.index(card_num[i])] = 1
            break
       
        elif card_S_sort[mid] > card_num[i]:
            high = mid - 1
            
        else:
            low = mid + 1

print(*result)

👉 생각 자체를 이진 탐색할 리스트를 card_S로 정했었다.
card_num에 있는 수를 card_S에 있는지 판단하는 것이므로 저렇게 정했던 것 같다.
그렇게 해서 출력 결과는 card_num의 결과이기 때문에 출력을 위한 result 리스트를 만들고
그 곳에 이진 탐색이 되면 그 인덱스에 해당하는 값을 result[card_S.index(card_num[i])] 이렇게
복잡하게 설정해서 1로 바꿔서 나중에 result를 출력하도록 했다.
물론, 정답은 맞았지만 시간이 초과됐다.
text로만 이렇게 써도 뭔가 복잡해보인다.

해결 포인트 1

1. 이진 탐색할 리스트를 card_num이 아니라 card_S로 설정한다.

import math
import sys
input = sys.stdin.readline
N = int(input())
card_num = list(map(int, input().split()))
M = int(input())
card_S = list(map(int, input().split()))

card_num_sort = sorted(card_num)

result = [0 for i in range(M)]

for i in range(M):
    low = 0
    high = N-1
    while low <= high:
        mid = (low + high) // 2
        
        if card_num_sort[mid] == card_S[i]:
            result[i] = 1
            break
        elif card_num_sort[mid] > card_S[i]:
            high = mid -1
        elif card_num_sort[mid] < card_S[i]:
            low = mid + 1

print(*result)

출력 결과가 결국 card_S의 결과이기 때문에 이진 탐색할 리스트로 card_S를 설정하여
result의 값을 변경하는 코드에서 result[card_S.index(card_num[i])] 이렇게 선언하여
card_S의 index를 찾는 시간을 쓰지 않아도 된다.
result[i] = 1 이렇게 변경할 수 있다.

👉 시간 초과도 되지 않고 정답으로 맞았지만, 다른 사람들의 풀이보다 시간이 월등히 오래 걸렸다.

따라서, 다른 사람들의 풀이를 보았다.

해결 포인트 2

2. set 함수 사용

n = int(input())
s_card = set(map(int, input().split()))

m = int(input())
card = list(map(int, input().split()))
lst = [0 for i in range(m)]

for i in range(m) :
    if card[i] in s_card :
        lst[i] += 1

for i in range(len(lst)) :
    print(lst[i], end = ' ')

👉 다른 사람의 풀이인데, set를 왜 쓰는지 몰랐다.
지금까지 내가 set를 알기로는, 중복을 제거하는 용도로 썼었는데
여기서는 중복도 없다고 문제 조건에 나와 있어서 의아했다.
찾아보니, set를 쓰면 탐색 시간 복잡도가 O(1)이 걸린다고 한다.

그래서, 저렇게 in으로 간단하게 처리할 수 있는 것도 리스트 상태에서는
시간 복잡도가 O(N^2)이 나와서 하지 않았는데 set는 O(1)이므로
저렇게 간단하게 구할 수 있었다.

set 함수의 용도
① 중복 제거
② 시간 복잡도 줄이기

---

list와 set, dictionary 주요 함수의 시간 복잡도를 정리한 페이지는 다음과 같다.
https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt