정렬된 배열에서 특정 수의 개수 구하기
📌문제N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하시오.단 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받습니다. 📌풀이모든 원소가 정렬이 된 상태로 입력되므로 이진 탐색을 이용하여 값이 x인 원소의 개수를 O(logN)에 찾아낼 수 있음수열 내 x가 존재한다면 연속적으로 나열되어 있음따라서 x가 처음 등장한 인덱스와 마지막으로 등장한 인덱스의 차를 계산 이진 탐색 함수 2개를 사용하여 문제 해결1. 가장 첫번째 위치를 찾는 이진 탐색 함수2. 가장 마지막 위치를 찾는 이진 탐색 함수 📌코드# 정렬된 수열에서 값이 x인 원소 개수를 세는 메서드def count_by_value(array, x)..
코딩테스트
2024. 12. 11. 10:34