부품 찾기(Python) - 이것이 코딩테스트다

부품 찾기(Python) - 이것이 코딩테스트다

 

 

 

문제 : 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.

 

N = 5

[8, 3, 7, 9, 2]

 

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품번호는 다음과 같다.

 

M = 3

[5, 7, 9]

이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

 

입력조건

• 첫째 줄에 정수 N이 주어진다. (1<=N<=1,000,000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
• 셋째 줄에는 정수 M이 주어진다.
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 10억 이하이다.

출력조건

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

해결방법 

1. 입력값이 N개 -> 100만개 , M개 ->10만개, 데이터의 범위는 10억이하이다.

2. M개의 배열에서 target을 가져오고, 이를 이진탐색에 넣는다.

3. 찾으면 yes를 호출하고 못찾으면 no를 호출한다.

 

def binary_search(array, target, start, end):
  if start > end :
    return None
  mid = (start+end)//2

  if array[mid] == target :
    return mid
  elif array[mid] > target :
    return binary_search(array, target, start ,mid-1)
  else :
    return binary_search(array, target, mid+1, end)


n= int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))


a.sort()

for i in range(m):
  target = b[i]
  result = binary_search(a, target, 0, n-1)
  if result == None:
    print("No", end = ' ')
  else :
    print("Yes", end = ' ')

 문제를 풀면서 알게 된 개념

1. sort함수를 이용할 때는 a = a.sort()가 아닌 a.sort()로 해야한다.

2. print()안에 변수를 썼을 때는 뒤에 , 없이 end = ' '가 가능했는데, 변수가 없다면 ,을 붙여주도록 하자.

 

문제 해설

- 데이터의 개수가 100,000개와 1,000,000개 인 것으로 보아 순차탐색으로 계산을 한다면 최대 1,000,000 X 100,000의 연산횟수가 나온다는 것을 알 수 있다. 이는 1000억에 가까운 수이므로 순차적으로 탐색은 해결방법이 아니다.

- 다음으로 생각한 건 이진 탐색이다. 이진 탐색은 정렬이 되어있는 숫자에서만 가능하기 때문에 먼저 a의 배열을 sort로 정렬을 해준다. 이는 병합 정렬의 시간 복잡도를 따르기에 O(NlogN)이다. 이 숫자는 약 2,000만에 가까운 수가 된다. 그리고 100,000 개의 데이터를 하나 가져와서 이진탐색을 수행한다면 logN만큼 하기에 이는 O(MlogN)이 든다고 할 수 있다. 그렇기에 위와 같은 방법으로 접근하면 문제를 해결 할 수 있다.

 

이 문제를 계수정렬을 이용해서도 풀 수 있다. 이것이 가능한 이유는 N개 각각의 값이 1부터 100만 사이이기 때문이다.

- 1,000,000개의 배열을 선언한 뒤 0으로 초기화 시키고, N개의 배열에 해당하는 값만 count를 1 증가시킨다.

- m개와 b배열을 입력받는다.

- b 배열에서 하나씩 빼와서 이를 a에서 인덱스로 취급해 값이 1 이 나온다면 yes 아니라면 no를 출력하도록 한다.

 

n = int(input())

a = [0] * 1000000

for i in input().split():
  a[int(i)] = 1
  
m = int(input())
x = list(map(int,input().split()))

for i in x :
  if a[i] == 1 :
    print('yes', end = ' ')
  else :
    print('no', end =' ')
    
    

 

계수정렬은 처음에 1,000,000만큼의 초기화, x리스트의 최대 개수값 100,000만큼만 수행이 이루어진다. 그렇기에 위의 이진탐색보다 더욱더 효과적이라고 볼 수 있다. 코드를 작성하면서 새로운 사실을 알게 되었는데 파이썬에서는 데이터의 개수와 무관하게 입력과 동시에 바로 변수로 쓸 수 있기 때문에 range(개수)하고 개수에 따라 값을 추가한다는 일이 딱히 필요가 없다. 이에 빨리 익숙해져야겠다. 

 

for i in input().split() 과 for i in 배열은 체화 시키는 게 좋을 듯하다.

 

마지막으로 set()함수를 이용한 풀이를 살펴보자

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

m = int(input())

x = list(map(int, input().split()))

for i in x :
  if i in array:
    print('yes', end = ' ')
  else :
    print('no', end =' ')

if i in array는 집합 자료형일 때 쓰는 것으로 보인다. 특정한 수가 있는지 없는지만 검사하면 되기 때문에 이를 사용하는 것도 효율적으로 보인다.