[이.취.코] Chap 15. 이진탐색 - Q27. 정렬된 배열에서 특정 수의 개수 구하기

1. 정렬된 배열에서 특정 수의 개수 구하기

  • 난이도
  • 풀이 시간
    • 30분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128 MB
  • 출처
    • Zoho 인터뷰

A. 📜 문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하라.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받는다.

a. 예를 들면.

수열 {1, 1, 2 ,2 ,2 ,2, 3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.

b. 입력 조건
  • 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력된다.
    • 1 <= N <= 1,000,000
    • -1e9 <= x <= 1e9
  • 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다
    • -1e9 <= 각 원소의 값 <= 1e9
c. 출력 조건

수열의 원소 중에서 값이 x인 원소의 개수를 출력한다. 단 값이 x인 원소가 하나도 없다면 -1일 출력한다.

d. 테스트 케이스
  • 입력 예시

    
    7 2
    1 1 2 2 2 2 3
    
    
    
    7 4
    1 1 2 2 2 2 3
    
    
  • 출력 예시

    
    4
    
    
    
    -1
    
    

B. 💡 내 답안

a. 😊 1차 시도 (성공)

def bi_sec(start, end, target, array):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid

        if array[mid] > target:
            end = mid -1
        elif array[mid] < target:
            start = mid + 1
    return 0

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

start = 0
end = n-1

pre = bi_sec(start, end, x-1, array)
post = bi_sec(start, end, x+1, array)

answer = (post - 1) - (pre + 1) + 1

if post - pre > 0:
    print(answer)
else:
    print(-1)

a. 🙄 회고

내 풀이

  • logN으로 탐색하는 것에서 이진탐색이 떠올랐다.

반성

  • 이진탐색 라이브러리도 있는데, 사용하지 못했다.
    • bisect

결론

  • 다음에 풀때는 이진탐색 라이브러리도 사용해봐야지

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

이진 탐색을 2번 돌리면 된다.

N개의 원소가 정수이기 때문에, 구하고자 하는 수 - 1구하고자 하는 수 + 1의 인덱스를 따로 구해서 빼주면 된다.

a. 책 답안

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

이 글이 도움이 되었나요?

신고하기
0분 전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.