정렬된 배열에서 특정 수의 개수 구하기 코드 및 해설 (파이썬)
2021. 6. 28. 10:36ㆍalgorithm
반응형
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 27, p 367
재귀함수로 구현한 이진 탐색 코드를 참고하여 풀이했습니다.
타겟 값이 있는 인덱스를 result라는 집합에 모두 추가하고 이 집합의 길이를 반환했습니다. 기존의 이진 탐색과 동일하지만, 중간값이 타겟과 같은 경우 현재 중간값을 result 집합에 추가해주었고, 왼쪽과 오른쪽 모두에 타겟이 더 있을 수 있으므로 end를 mid-1로 갱신한 탐색, start를 mid+1로 갱신한 탐색 모두를 진행하도록 했습니다. 타겟 원소가 하나도 없으면 -1을 출력하도록 했으므로 result의 길이가 0보다 크면 len(result)를, 그렇지 않으면 -1을 출력하도록 했습니다.
https://codlingual.tistory.com/189
# 이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, target, start, end, result):
if start > end:
# x인 원소가 하나도 없다면 -1 출력
return len(result) if len(result) > 0 else -1
mid = (start + end) // 2
# 중간값이 타겟인 경우
if array[mid] == target:
# 현재 인덱스를 result 집합에 추가
result.add(mid)
# 현재 인덱스보다 작은 쪽, 큰 쪽 모두 가보기
binary_search(array, target, start, mid - 1, result)
binary_search(array, target, mid + 1, end, result)
# 중간값이 타겟보다 큰 경우
elif array[mid] > target:
binary_search(array, target, start, mid - 1, result)
# 중간값이 타겟보다 작은 경우
else:
binary_search(array, target, mid + 1, end, result)
# x인 원소가 하나도 없다면 -1 출력
return len(result) if len(result) > 0 else -1
def solution(N, x, array):
return binary_search(array, x, 0, N-1, result=set())
반응형
'algorithm' 카테고리의 다른 글
백준 공유기 설치 코드 및 해설 (파이썬) (0) | 2021.06.30 |
---|---|
고정점 찾기 코드 및 해설 (파이썬) (0) | 2021.06.29 |
이진 탐색 (0) | 2021.06.28 |
리트코드 Recover Binary Search Tree 코드 및 해설 (파이썬) (0) | 2021.06.27 |
리트코드 Populating Next Right Pointers in Each Node 코드 및 해설 (파이썬) (0) | 2021.06.23 |