이 문제에서는 정렬되지 않은 n개의 정수로 구성된 배열 arr[]와 하나의 정수 val이 주어집니다. 우리의 목표는 정렬되지 않은 배열 안에서 해당 요소가 위치한 시작 인덱스와 끝 인덱스를 찾는 것입니다.
요소가 배열에 등장하는 횟수에 따라 결과를 아래와 같이 출력해야 합니다.
- 요소가 배열에 두 번 이상 존재하는 경우 → 시작 인덱스와 끝 인덱스를 출력
- 요소가 배열에 한 번만 존재하는 경우 → 해당 단일 인덱스를 출력
- 요소가 배열에 존재하지 않는 경우 → "요소가 배열에 없음"을 출력
문제 이해를 위한 예제
예제 1
입력 : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2
출력 : 시작 인덱스 = 0, 끝 인덱스 = 5설명: 요소 2는 배열에 두 번 등장합니다. 첫 번째는 인덱스 0, 두 번째는 인덱스 5에 위치합니다.
예제 2
입력 : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5
출력 : 인덱스 2에 한 번만 존재설명: 요소 5는 배열 전체에서 인덱스 2에 딱 한 번만 나타납니다.
예제 3
입력 : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 7
출력 : 배열에 존재하지 않습니다!해결 접근 방식
가장 간단한 해결 방법은 양방향 탐색(Two-way Traversal)입니다. 배열을 앞과 뒤에서 동시에 순회하며 목표 값을 찾는 방식으로, 불필요한 반복을 줄여 효율적입니다.
구체적으로는 first와 last라는 두 개의 인덱스 변수를 사용합니다. first는 배열의 처음부터 앞으로 이동하고, last는 배열의 끝에서부터 뒤로 이동합니다. 두 인덱스가 가리키는 값이 모두 val과 일치하게 되면 탐색을 종료합니다.
알고리즘 단계
- 1단계 − 배열을 순회합니다.
- 1.1단계 −
first인덱스는 배열의 시작 부분부터,last인덱스는 끝 부분부터 탐색에 사용합니다. - 1.2단계 − 현재 인덱스의 값이
val과 같다면 해당 인덱스를 더 이상 이동시키지 않습니다. - 1.3단계 − 두 인덱스가 가리키는 값이 모두 같으면(즉,
val을 만나면) 루프를 종료합니다.
- 1.1단계 −
C++ 구현 예제
아래 프로그램은 위에서 설명한 해결 방법의 동작을 보여줍니다.
#include <iostream>
using namespace std;
void findStartAndEndIndex(int arr[], int n, int val) {
int start = 0;
int end = n - 1;
while(1){
if(arr[start] != val)
start++;
if(arr[end] != val)
end--;
if(arr[start] == arr[end] && arr[start] == val)
break;
if(start == end)
break;
}
if (start == end ){
if(arr[start] == val)
cout<<"요소가 인덱스 "<<start<<" 에서 한 번만 발견되었습니다.";
else
cout<<"배열에 해당 요소가 존재하지 않습니다.";
} else {
cout<<"요소가 두 번 이상 존재합니다\n";
cout<<"시작 인덱스: "<<start<<endl;
cout<<"마지막 인덱스: "<<end;
}
}
int main() {
int arr[] = { 2, 1, 5, 4, 6, 2, 9, 0, 2, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int val = 2;
findStartAndEndIndex(arr, n, val);
return 0;
}
실행 결과
요소가 두 번 이상 존재합니다
시작 인덱스: 0
마지막 인덱스: 8
시간 복잡도 분석
이 알고리즘은 배열을 앞뒤에서 동시에 탐색하므로 최악의 경우에도 전체 배열을 한 번씩만 확인합니다. 따라서 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 정렬되지 않은 배열에서 특정 값의 범위를 찾아야 할 때 매우 실용적인 접근 방식입니다.