1부터 n까지의 숫자로 이루어진 배열이 주어졌을 때, 이 배열을 오름차순으로 정렬하는 데 필요한 '맨 앞으로 이동(move-to-front)' 연산의 최소 횟수를 구하는 것이 목표입니다. 배열에는 중복된 값이 없으며, '맨 앞으로 이동' 연산이란 특정 요소를 선택하여 배열의 첫 번째 위치(인덱스 0)로 옮기는 작업을 의미합니다.
문제를 해결하려면 배열을 뒤에서부터 앞으로 순회하면서 각 요소가 올바른 위치에 있는지 확인합니다. 올바른 위치에 있는 요소라면 추가 이동이 필요 없고, 그렇지 않다면 이동이 필요합니다. 1부터 n까지의 값을 가지는 배열에서는 arr[0]은 1, arr[1]은 2, … arr[n-1]은 n이 되어야 하므로, arr[i]의 올바른 값은 i+1입니다.
예제 1
입력
Arr[]= { 4,3,2,1 }출력
최소 '맨 앞으로 이동' 연산 횟수: 3
풀이 과정
3을 앞으로 이동 → 3,4,2,1 (count=1) 2를 앞으로 이동 → 2,3,4,1 (count=2) 1을 앞으로 이동 → 1,2,3,4 (count=3)
예제 2
입력
Arr[]= { 6,1,2,5,4,3 }출력
최소 '맨 앞으로 이동' 연산 횟수: 5
풀이 과정
5를 앞으로 이동 → 5,6,1,2,4,3 (count=1) 4를 앞으로 이동 → 4,5,6,1,2,3 (count=2) 3을 앞으로 이동 → 3,4,5,6,1,2 (count=3) 2를 앞으로 이동 → 2,3,4,5,6,1 (count=4) 1을 앞으로 이동 → 1,2,3,4,5,6 (count=5)
알고리즘 접근 방식
정수 배열 Arr[]에는 1부터 n까지의 숫자가 저장됩니다.
정수 변수 size는 배열 Arr[]의 길이를 저장합니다.
movetoFront(int arr[], int n) 함수는 배열과 그 길이를 입력받아, 해당 배열을 정렬하는 데 필요한 최소 '맨 앞으로 이동' 연산 횟수를 반환합니다.
count 변수는 배열의 크기(n)로 초기화합니다. 배열이 완전히 내림차순으로 정렬되어 있는 경우 모든 요소를 이동해야 할 수 있기 때문입니다.
마지막 인덱스부터 앞쪽 방향으로 순회하면서, 현재 요소의 값이 count와 같은지 확인합니다. 1부터 n 사이의 정렬된 배열에서는 n이 마지막 위치, n-1이 마지막에서 두 번째 위치에 있어야 하므로, 값이 일치한다면 해당 요소는 이미 올바른 위치에 있는 것입니다. 이 경우 count를 1 감소시킵니다.
순회가 끝나면 count에는 실제로 이동이 필요한 요소의 개수, 즉 원하는 결과가 저장됩니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간 없이 해결할 수 있는 효율적인 방법입니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
// 배열을 오름차순으로 정렬하는 데 필요한
// 최소 이동 횟수를 계산하는 함수
int movetoFront(int arr[], int n){
// 모든 요소가 올바르게 배치되어 있다고 가정하고 count 초기화
int count = n;
// 배열을 끝에서부터 순회
for (int i=n-1; i >= 0; i--){
// 현재 요소가 올바른 위치에 있다면 count 감소
// 범위가 1부터 n이므로 arr[i]의 값은 i+1이어야 함
// 인덱스 0에는 1, 인덱스 1에는 2, ...
if (arr[i] == count)
count--;
}
return count;
}
int main(){
int Arr[] = {5, 3, 4, 7, 2, 6, 1};
int size = 7;
cout << "배열 정렬을 위한 최소 '맨 앞으로 이동' 횟수: " << movetoFront(Arr, size);
return 0;
}실행 결과
배열 정렬을 위한 최소 '맨 앞으로 이동' 횟수: 6