Q27. 정렬된 배열에서 특정 수의 개수 구하기
🐣문제
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. (단, 특정 값의 원소가 하나도 없다면 -1을 출력합니다.)
🐥풀이
이진 탐색으로 풀어보자!
이진 탐색이란?
오름차순으로 정렬된 배열(리스트)에서 특정 값의 위치를 찾는 알고리즘이다. 처음과 끝의 중간 값을 찾고 크고 작음을 비교해가며 특정 값의 위치를 찾아간다.
예를 들어보면, 처음(start)과 끝(end)의 중간점(mid)을 찾으면 위의 그림과 같다. 여기서 target1의 값을 찾아보자. target1은 중간점(mid)의 위치보다 왼쪽에 있다. 즉, 오름차순 정렬이므로 중간점(mid) 위치의 값보다 target1의 값이 작다. 그럼 왼쪽에서 다시 탐색하여 target1을 찾아야 한다.
end점을 중간점(mid) 왼쪽으로 옮겼다. 즉, end점을 mid-1의 위치로 옮겼다. 그리고 다시 start점과 end점의 중간점을 찾아보자. 중간점의 위치와 target1의 위치가 일치한다. 그럼 찾고자 했던 target1의 위치를 찾은 것이다.
반대로, target2를 찾아보자. target2는 처음 중간점(mid)보다 오른쪽에 있다. 즉, 중간점(mid) 위치의 값보다 target2의 값이 더 크다. 그럼 start점을 중간점(mid) 오른쪽으로 옮긴다. start점을 mid+1의 위치로 옮기는 것이다. 그리고 다시 start점과 end점의 중간점을 찾아보면, 중간점의 위치와 target2의 위치가 일치한다. target2를 찾았다!
위와 같은 이진 탐색 알고리즘을 활용해보자! 특정 값의 개수를 찾아야하므로,
1. 우선 특정 값의 위치를 찾는다.
2. 왼쪽과 오른쪽으로 특정 값이 몇 개씩 있는 지를 판단한다.
(단, 여기서 왼쪽 또는 오른쪽으로 탐색해나가면서 특정 값이 없어지면 break 한다. 오름차순 정렬이므로 한번 특정 값이 없으면 같은 방향으로 계속 탐색해나가도 특정 값은 없다.)
3. 왼쪽과 오른쪽에서 탐색하며 구한 특정 값의 개수를 합하여 결과를 출력한다.
🐓코드
n, x = map(int,input().split())
num = list(map(int, input().split()))
start, end, total = 0, len(num)-1, 0
while start<=end:
mid = (start+end)//2
# 중간점과 특정 값이 일치
if num[mid]==x:
for i in range(mid, -1, -1):
if num[i]==x:
total += 1
# 정렬된 배열이므로 특정 수가 아니면 그 뒤로 안 나옴
else:
break
for j in range(mid+1, len(num)):
if num[j]==x:
total += 1
else:
break
break
elif num[mid]>x:
end = start-1
else:
start = end+1
# 이진 탐색 끝
if total==0:
print(-1)
else:
print(total)⭐2022.05.02
파이썬 활용이라 스터디 중 코드리뷰에서는 count 함수를 써서 바로 구했는데, 이진탐색으로 다시 풀어보니 신박해!
