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

C++로 배열의 모든 요소를 동일하게 만드는 최소 이동 횟수 구하기

문제 개요

N개의 요소로 이루어진 배열과 정수 K가 주어집니다. 이 배열에는 다음과 같은 연산을 원하는 만큼 반복해서 수행할 수 있습니다.

  • 배열의 K번째 요소를 배열의 맨 뒤에 삽입하고, 동시에 배열의 첫 번째 요소를 삭제합니다.

목표는 이 연산을 활용해 배열의 모든 요소를 동일한 값으로 만드는 데 필요한 최소 이동 횟수를 구하는 것입니다. 만약 어떻게 해도 모든 요소를 같게 만들 수 없다면 -1을 출력해야 합니다.

예시

배열이 arr[] = {1, 2, 3, 4, 5, 6}이고 k = 6인 경우, 최소 5번의 이동이 필요합니다.

Move-1: {2, 3, 4, 5, 6, 6}
Move-2: {3, 4, 5, 6, 6, 6}
Move-3: {4, 5, 6, 6, 6, 6}
Move-4: {5, 6, 6, 6, 6, 6}
Move-5: {6, 6, 6, 6, 6, 6}

매 이동마다 6번째 요소(값 6)가 뒤에 추가되고 첫 번째 요소가 제거되면서 배열이 한 칸씩 앞당겨지고, 결국 모든 값이 6으로 통일되는 과정을 확인할 수 있습니다.

알고리즘 접근 방법

  1. 연산이 진행되면 먼저 a[k]가 배열 끝으로 복사되고, 이후 a[k+1], a[k+2]… 순서대로 차례차례 뒤에 붙습니다.
  2. 복사되는 값들이 모두 같도록 보장하려면, 인덱스 K부터 N까지의 모든 요소가 서로 동일해야 합니다. 아울러 인덱스 1부터 K 사이에서 a[k]와 값이 다른 요소들은 모두 제거 대상이 됩니다.
  3. 따라서 인덱스 1~K 범위에서 a[k]와 다른 값을 가진 요소 중 가장 오른쪽에 있는 항목에 도달할 때까지 연산을 계속 적용하면 됩니다.

C++ 구현 코드

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int getMinMoves(int *arr, int n, int k){
    int i;
    // 1) k-1번째부터 배열 끝까지 모든 요소가 arr[k-1]과 같은지 검사
    for (i = k - 1; i < n; ++i) {
        if (arr[i] != arr[k - 1]) {
            return -1;
        }
    }
    // 2) 0 ~ k-2 범위에서 arr[k-1]과 다른 값을 가진
    //    가장 오른쪽 요소의 위치를 찾아 이동 횟수 반환
    for (i = k - 1; i >= 0; --i) {
        if (arr[i] != arr[k - 1]) {
            return i + 1;
        }
    }
    // 이미 모든 요소가 같은 경우
    return 0;
}

int main(){
    int arr[] = {1, 2, 3, 4, 5, 6};
    int k = 6;
    cout << "Minimum moves required = " << getMinMoves(arr, SIZE(arr), k) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일한 뒤 실행하면 다음과 같은 출력을 얻을 수 있습니다.

Minimum moves required = 5

정리

핵심 아이디어는 두 단계로 나눌 수 있습니다. 첫째, K번째 위치 이후의 요소들이 전부 같지 않다면 아무리 연산을 반복해도 배열을 균일하게 만들 수 없으므로 -1을 반환합니다. 둘째, 그렇지 않다면 앞부분(K 이전 구간)에서 기준 값과 다른 요소 중 가장 오른쪽에 있는 위치가 곧 필요한 최소 이동 횟수가 됩니다. 이 풀이는 배열을 최대 두 번 선형 탐색하므로 시간 복잡도는 O(N)이며, 추가 메모리 없이 해결할 수 있는 효율적인 방법입니다.