[이코테] CH07 이진 탐색 실전문제 2번 부품 찾기

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")

이런 식으로 하는게 코드가 가장 간결할 것이다.