Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 k 이하의 모든 요소를 한데 모으는 데 필요한 최소 스왑 횟수 구하기

문제 정의

양의 정수 n개로 이루어진 배열과 하나의 숫자 k가 주어집니다. 이때, k보다 작거나 같은 모든 숫자들을 서로 인접한 위치에 모으기 위해 필요한 최소 스왑(교환) 횟수를 구하는 것이 목표입니다.

예시

입력 배열이 {1, 5, 4, 7, 2, 10}이고 k = 6이라고 가정해 봅시다. 이 경우 7과 2를 한 번 교환하면 되므로, 필요한 최소 스왑 횟수는 1회입니다.

알고리즘 접근 방식

이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

  • 1단계: 배열에서 k보다 작거나 같은 요소의 개수를 셉니다. 이 개수를 'cnt'라고 합니다.
  • 2단계:
  • 길이가 'cnt'인 윈도우(구간)를 두 포인터(two pointer) 기법으로 탐색하면서, 각 윈도우 안에 k보다 큰 요소가 몇 개 있는지 센 후 그 합계를 'outOfRange'라고 합니다.
  • 3단계: 길이가 'cnt'인 모든 윈도우에 대해 2단계를 반복하고, 그중 'outOfRange' 값이 가장 작은 경우를 찾습니다. 이 값이 곧 최종 답이 됩니다.

직관적으로 설명하면, k 이하의 숫자들이 최종적으로 모여야 할 자리는 연속된 'cnt'칸입니다. 따라서 어떤 윈도우에 k보다 큰 숫자가 적게 들어 있는지를 찾으면, 그 숫자들만 바깥의 요소와 교환하면 되기 때문에 해당 윈도우 내부의 'k 초과' 요소 개수가 곧 필요한 스왑 횟수와 일치합니다.

C++ 구현 예제

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

int getMinSwaps(int *arr, int n, int k) {
    // k 이하의 요소 개수 계산
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] <= k) {
            ++cnt;
        }
    }

    // 첫 번째 윈도우에서 k보다 큰 요소 개수 계산
    int outOfRange = 0;
    for (int i = 0; i < cnt; ++i) {
        if (arr[i] > k) {
            ++outOfRange;
        }
    }

    int result = outOfRange;

    // 슬라이딩 윈도우: 윈도우를 한 칸씩 이동하며 최솟값 갱신
    for (int i = 0, j = cnt; j < n; ++i, ++j) {
        if (arr[i] > k) {
            --outOfRange;
        }
        if (arr[j] > k) {
            ++outOfRange;
        }
        result = min(result, outOfRange);
    }
    return result;
}

int main() {
    int arr[] = {1, 5, 4, 7, 2, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    cout << "Minimum swaps = " << getMinSwaps(arr, n, k) << endl;
    return 0;
}

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

실행 결과

Minimum swaps = 1

시간 복잡도 분석

배열을 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가적인 메모리 사용 없이 상수 공간 O(1)만으로 해결할 수 있습니다. 완전 탐색 방식(O(n × cnt))에 비해 훨씬 효율적이기 때문에, 슬라이딩 윈도우 기법은 이 유형의 문제에서 가장 널리 사용되는 최적화 전략입니다.