접근법
A와 X의 원소를 각각 순회하며 검색(선형탐색)했으나, 결과는 시간 초과로 인한 실패다. 단순 선형탐색을 개선한 보초법도 역시 시간 초과가 뜬다.
# """선형탐색"""
from typing import Any, Sequence
import copy
import sys
def seq_search(seq: Sequence, key: Any) -> int:
"""시퀀스 a에서 key와 값이 같은 원소를 선형 검색(while문)"""
# i = 0
# while True:
# if i == len(a):
# return -1 # 검색에 실패하여 -1을 반환
# if a[i] == key:
# return i
# i += 1
"""시퀀스 seq에서 key와 일치하는 원소를 선형 검색(보초법)"""
a = copy.deepcopy(seq) # seq를 복사
a.append(key) # 보초 key를 추가
i = 0
while True:
if a[i] == key:
break
i += 1
return -1 if i == len(seq) else i
if __name__ == '__main__':
N = int(sys.stdin.readline())
A = [None] * N
A = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
B = list(map(int, sys.stdin.readline().split()))
for i in range(N):
idx = seq_search(A, B[i])
if idx == -1:
print(0)
else:
print(1)풀이법
구글링 하면서 보다 더 효율적인 이진탐색을 공부했다.
상기 블로그에 있는 내용이 이분탐색 알고리즘을 이해하기 가장 좋았다.
배열 인덱스 값을 기준으로 LEFT, RIGHT를 설정하고 (LEFT+RIGHT) // 2 로 MID를 구해서 내가 찾는 값이 맞는지 비교하고, 아니라면 LEFT, RIGHT, MID를 다시 설정해나가며 탐색하는 알고리즘이다.
from sys import stdin, setrecursionlimit
N = int(stdin.readline())
A = sorted(map(int, stdin.readline().split())) # 오름차순으로 원소를 정렬한 후 배열에 저장
M = int(stdin.readline())
X = list(map(int, stdin.readline().split())) # X는 정렬하지 않아도 된다
def binary_search(x):
left = 0
right = len(A)-1
while left <= right:
mid = (left+right) // 2
if A[mid] == x:
return 1
elif x < A[mid]:
right = mid - 1
elif x > A[mid]:
left = mid + 1
for i in range(M):
if binary_search(X[i]):
print(1)
else:
print(0)
해당 문제는 이분탐색 외에도 set()과 in 연산자를 활용해 풀 수도 있다.
