알고리즘 문제 풀이/이코테
[이코테] CH07 이진 탐색 실전문제 2번 부품 찾기
파란색 가운
2024. 1. 5. 16:47
import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def findelem(arr,targetElement):
start = 0
end = len(arr)
while start<=end:
mid = (start + end) // 2
if arr[mid] == targetElement:
return "yes"
elif arr[mid] > targetElement:
end = mid - 1
else:
start = mid + 1
return "no"
N = int(input())
arr = list(map(int,sys.stdin.readline().split()))
M = int(input())
target = list(map(int,sys.stdin.readline().split()))
arr.sort()
for i in target:
print(findelem(arr,i),end=' ')
이렇게 푸는것이 정석이지만
계수정렬로 푸는게 훨씬 간단하다고 생각했다.
문제에서 N의 크기가 100만 이상으론 가지 않는다고 명시해줬으므로
2번째 배열의 크기를 100만 + 1으로 만들어주고,
부품 번호의 인덱스를 1로 만들어준다.
예를 들어 문제에선 2 3 7 8 9 이므로
arr[2],arr[3],arr[7],arr[8],arr[9]의 값을 1로 초기화(나머진 모두 초기에 0으로 초기화)
이후 target 배열의 반복문에서
for i in target:
if i in arr:
print("yes")
이런 식으로 하는게 코드가 가장 간결할 것이다.