[파이썬 알고리즘] 부품 찾기 문제 풀이
업데이트:
❓ 문제
💡 문제 해결 아이디어
- 매장 내 N개의 부품을 번호 기준으로 정렬
- M개의 찾고자 하는 부품이 각각 매장에 존재하는지 검사
✔️ 파이썬 답안 예시
이진 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 이진 탐색 소스코드 구현 (반복문)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
end = mid - 1
# 중간점의 값보다 찾고자 하는 값이 작은 경우 오른쪽 확인
else:
start = mid + 1
return None
# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백을 기준으로 구분하여 입력
array = list(map(int, input().split()))
array.sort() # 이진 탐색을 수행하기 위해 사전에 정렬 수행
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
result = binary_search(array, i, 0, n - 1)
if result != None:
print('yes', end=' ')
else:
print('no', end=' ')
정렬
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# N(가게의 부품 개수) 입력
n = int(input())
array = [0] * 1000001
# 가게에 있는 전체 부품 번호를 입력 받아서 기록
for i in input().split():
array[int(i)] = 1
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if array[i] == 1:
print('yes', end=' ')
else:
print('no', end=' ')
set()
set() 함수는 파이썬에서 집합을 표현할 때 사용하는 자료형으로 특정한 데이터가 존재하는지 검사할 때 매우 효과적이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 입력 받아서 집합(Set) 자료형에 기록
array = set(map(int, input().split()))
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))
# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
# 해당 부품이 존재하는지 확인
if i in array:
print('yes', end=' ')
else:
print('no', end=' ')
Notice: 이 게시물은 한빛미디어의 이것이 코딩 테스트다 교재를 참고하였습니다.
댓글남기기