C++ 정렬 회전 배열에서 주어진 값 이하의 요소 개수 구하기

문제 소개

정수로 이루어진 배열이 하나 주어집니다. 이 배열은 정렬된 상태에서 회전(rotated)된 배열, 즉 '정렬 회전 배열'입니다. 우리의 목표는 배열 안에서 주어진 숫자 K보다 작거나 같은 요소가 몇 개인지 찾아내는 것입니다.

가장 직관적인 접근 방법은 배열 전체를 한 번 순회하면서 K 이하인 요소의 개수를 세는 것입니다.

입력 및 출력 예시

예시 1

Arr[] = { 1, 2, 3, 4, 9, 8, 10 }, K = 4

결과:

4 이하인 요소의 개수 : 4

설명 — 4 이하인 요소는 1, 2, 3, 4이므로 개수는 4개입니다.

예시 2

Arr[] = { 5, 3, 6, 1, 8, 100, 12, 31 }, K = 3

결과:

3 이하인 요소의 개수 : 2

설명 — 3 이하인 요소는 1과 3이므로 개수는 2개입니다.

알고리즘 접근 방식

• 정수 배열 Arr[]에 데이터를 저장하고, 기준이 되는 값을 K로 나타냅니다.

• 정수 변수 n에는 배열의 길이(요소 개수)를 저장합니다.

• 변수 count는 K보다 작거나 같은 숫자의 개수를 저장하는 데 사용합니다.

• 배열의 첫 번째 요소(인덱스 0)부터 끝까지 한 번 순회합니다.

• 현재 요소가 K 이하라면 count를 1 증가시킵니다.

• 순회가 끝난 후 count 변수에 원하는 결과가 담겨 있습니다.

• 결과를 화면에 출력합니다.

C++ 구현 코드

#include <iostream>
using namespace std;
int main(){
    int Arr[]= { 4,5,8,1,3,7,10,9,11 };
    int k=7;
    int n=sizeof(Arr)/sizeof(Arr[0]);
    int count=0;
    for(int i=0;i<n;i++)
        if(Arr[i]<=k)
            count++;
        std::cout<<"Elements less than or equal to "<<k<<" in given sorted rotated array : "<<count;
    return 0;
}

실행 결과

Elements less than or equal to 7 in given sorted rotated array : 5

정리

위 방법은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 정렬 회전 배열이라도 단순 선형 탐색으로 충분히 빠르게 답을 구할 수 있으며, 만약 배열이 완전히 정렬되어 있다면 이진 탐색(binary search)을 활용해 O(log n)으로 더 최적화할 수도 있습니다.