[이진 탐색] 부품 찾기 (실전문제, 이것이 코딩테스트다 with 파이썬)

이진 탐색(Binary Search)

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터 찾는 방법

• 탐색 범위를 절반씩 좁혀가며 데이터 탐색
• 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터 찾을 수 있음
• 위치 변수 3개(시작점, 중간점, 끝점) 사용
• 한 번 확인할 때마다 원소의 개수 절반씩 줄어듦 → 시간 복잡도 O(logN)
  (단계마다 2로 나누는 것과 동일)

 

문제

해설

• 여러 방법으로 해결할 수 있는 문제, 이진 탐색 알고리즘으로 풀이
• 매장 내 N개의 부품을 번호를 기준으로 정렬, M개의 찾고자 하는 부품이 매장에 존재하는지 검사
• 시간 복잡도 계산
  - 부품을 찾는 과정 : 최악의 경우 O(M x logN)의 연산
  - N개 부품 정렬 : 시간 복잡도 O(N x logN)
  - 이진 탐색 문제 풀이 : O((M + N) x logN)

 

풀이1 : 이진 탐색

# 함수 : 이진 탐색 소스코드 구현(반복문)
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 가게 부품 개수, array 가게 부품 번호, M 손님 부품 개수, X 손님 부품 번호
# N(가게의 부품 개수) 입력
n = int(input())

# 가게에 있는 전체 부품 번호를 공백으로 구분하여 입력
array = list(map(int, input().split()))
array.sort()    # 이진 탐색을 수행하기 위해 사전에 정렬 수행

# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())

# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(mp(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

변수 : N 가게 부품 개수, array 가게 부품 번호, M 손님 부품 개수, X 손님 부품 번호

 

1. 이진 탐색 함수 구현

ㄴ 데이터  >  중간점 : 중간점=시작점, 중간점=(끝점-시작점)//2    → 오른쪽에 존재

ㄴ 데이터 == 중간점 : 데이터 = 중간점

ㄴ 데이터  <  중간점 : 중간점=끝점, 중간점=(끝점-시작점)//2        → 왼쪽에 존재

2. 변수 n, array, m, x 입력받기

3. 손님 부품 번호와 가게 부품 개수 대조(이진 탐색 함수 호출)

 

풀이2 : 계수 정렬

# 변수 : N 가게 부품 개수, array 가게 부품 번호, M 손님 부품 개수, X 손님 부품 번호
# 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=' ')

 

해석2

변수 : N 가게 부품 개수, array 가게 부품 번호, M 손님 부품 개수, X 손님 부품 번호

 

1. 모든 원소의 번호 포함할 수 있는 크기의 리스트 생성 : array

2. N 입력받고, array에 가게 부품 번호 업데이트

3. M, X 입력받기

4. array와 X의 내용 대조하여 출력

 

풀이3 : 집합 자료형

# 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=' ')

 

해석3

단순히 특정한 수가 한 번이라도 등장했는지 검사

→ 집합 자료형 set( ) 함수 : 단순히 특정 데이터가 존재하는지 검사할 때 매우 효과적, 소스코드 간결