C++로 정찰 부대를 구성할 병사 쌍의 인덱스 찾기

원형으로 서 있는 n명의 병사가 있고, 각 병사의 키는 배열 A에 저장되어 있다고 가정해 봅시다. i번째 병사의 키는 A[i]입니다. 이때 정찰 부대(reconnaissance unit)는 키 차이가 가장 작은 두 명의 인접한 병사로 구성됩니다. 키가 비슷할수록 서로 곁에 있을 때 눈에 덜 띄기 때문입니다. 우리의 목표는 정찰 부대를 구성할 수 있는 병사 쌍의 인덱스를 찾는 것입니다.

예를 들어 입력이 A = [10, 12, 13, 15, 10]이라면, 출력은 (5, 1)이 됩니다. 마지막 병사(키 10)와 첫 번째 병사(키 10)의 키 차이가 0으로 가장 작기 때문입니다.

문제 해결 접근 방식

병사들이 원형으로 배치되어 있으므로, 마지막 병사와 첫 번째 병사도 서로 인접한 것으로 간주해야 합니다. 따라서 다음 단계로 문제를 해결할 수 있습니다.

• 먼저 마지막 병사와 첫 번째 병사의 키 차이를 초기 최솟값 D로 설정합니다.
• 배열을 순회하면서 인접한 두 병사의 키 차이를 계산합니다.
• 현재 최솟값 D보다 작은 차이가 발견되면 D와 해당 위치 H를 갱신합니다.
• 최종적으로 H와 (H mod n) + 1을 출력하여 원형 구조에서의 인접 쌍을 나타냅니다.

알고리즘 의사 코드

n := 배열 A의 크기
D := |A[0] - A[n - 1]|
H := n
i := 1부터 i < n까지 반복:
    만약 D > |A[i] - A[i - 1]| 이면:
        D := |A[i] - A[i - 1]|
        H := i
H와 (H mod n) + 1 출력

C++ 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A) {
    int n = A.size();
    int D = abs(A[0] - A[n - 1]);
    int H = n;
    for (int i = 1; i < n; i++) {
        if (D > abs(A[i] - A[i - 1])) {
            D = abs(A[i] - A[i - 1]);
            H = i;
        }
    }
    cout << H << ", " << (H % n) + 1;
}
int main() {
    vector<int> A = { 10, 12, 13, 15, 10 };
    solve(A);
}

입력

{ 10, 12, 13, 15, 10 }

출력

5, 1

시간 복잡도 분석

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 상수 공간 O(1)로 해결할 수 있습니다. 병사의 수가 많아져도 효율적으로 동작하는 장점이 있습니다.