문제 개요
이 글에서는 주어진 수열에서 모든 요소가 특정 값 X보다 큰 연속된 구간(segment)의 개수를 구하는 방법을 다룹니다.
겹치는 구간은 한 번만 계산하고, 인접한 두 요소나 구간을 서로 다른 구간으로 따로 세지 않는다는 점에 유의해야 합니다. 아래는 문제의 기본 예시입니다.
입력 : arr[ ] = { 9, 6, 7, 11, 5, 7, 8, 10, 3 }, X = 7
출력 : 3
설명 : { 9 }, { 11 }, { 8, 10 }이 7보다 큰 요소들로만 이루어진 구간입니다.
입력 : arr[ ] = { 9, 6, 12, 2, 11, 14, 8, 14 }, X = 8
출력 : 4
설명 : { 9 }, { 12 }, { 11, 14 }, { 14 }가 8보다 큰 요소들로만 이루어진 구간입니다.풀이 접근 방법
단순 순회 방식(Naive Approach)
변수 state를 0으로 초기화한 뒤 배열을 처음부터 끝까지 순회합니다. X보다 큰 요소를 만나면 state를 1로 설정하고, X 이하의 수를 만나면 state를 다시 0으로 되돌립니다. 그리고 state가 1에서 0으로 전환될 때마다 count를 1씩 증가시키면, 조건을 만족하는 구간의 개수를 셀 수 있습니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int main (){
int a[] = { 9, 6, 12, 2, 11, 14, 8, 14 };
int n = sizeof (a) / sizeof (a[0]);
int X = 8;
int state = 0;
int count = 0;
// 배열 순회
for (int i = 0; i < n; i++){
// 요소가 X보다 큰지 확인
if (a[i] > X){
state = 1;
}
else{
// state가 1인 경우 구간 하나 완성
if (state)
count += 1;
state = 0;
}
}
// 마지막 구간 처리
if (state)
count += 1;
cout << "모든 요소가 X보다 큰 구간의 개수: " << count;
return 0;
}
실행 결과
모든 요소가 X보다 큰 구간의 개수: 4
코드 설명
위 프로그램에서는 state를 스위치처럼 활용합니다. X보다 큰 수를 발견하면 state를 1로 설정하고, X 이하의 수를 발견하면 0으로 되돌립니다. state가 1이었다가 0으로 돌아올 때마다 count를 1 증가시켜 구간 하나가 완성된 것으로 간주하며, 마지막에는 count에 저장된 결과를 출력합니다.
특히 주의할 점은 배열의 마지막 요소까지 X보다 커서 구간이 배열 끝에서 끝나는 경우입니다. 이 경우 반복문 내부에서 count가 증가하지 않으므로, 반복문이 끝난 후 state 값을 한 번 더 검사하여 마지막 구간도 반드시 결과에 포함시켜야 합니다.
복잡도 분석
이 알고리즘은 배열을 딱 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다. 매우 효율적인 선형 탐색 기반 풀이입니다.
마무리
이 글에서는 state 플래그를 활용한 단순 순회 방식으로, 모든 요소가 X보다 큰 구간의 개수를 구하는 문제를 해결했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있으므로, 상태 전환(state toggle) 패턴을 응용한 대표적인 배열 순회 문제로 기억해 두면 좋습니다.