[백준 1083번] 소트

문제 링크: https://www.acmicpc.net/problem/1083

1083번: 소트

<문제 풀이> 그리디 알고리즘

 

연속된 두 개의 원소를 교환해서 "사전순으로 가장 뒤에 오는 배열"을 만드는 방법은 A[i-1]까지 정렬이 되어 있다고 했을 때 A[i]에 A[i +1], A[i + 2], ...A[i + n - 1]까지의 원소 중에서 최댓값이 A[i] 위치에 오면 되고 모든 A[i]에 대해서 반복하면 됩니다.

 

예를 들어 아래와 같은 배열이 있을 때

 

index 0 1 2 3 4

value 7 1 2 3 4  

 

A[0]은 주어진 배열에서 최댓값이니 A[0]까지의 원소는 정렬된 상태입니다.

A[1]에 A[2], A[3], A[4] 의 수 중에서 최댓값인 A[4]가 [1] 위치에 오면 A[1]까지의 원소는 정렬이 된 상태가 됩니다.

 

index 0 1 2 3 4

value 7 4 1 2 3

 

이때 A[4]의 원소가 A[1]로 가기 위해선  A[4]부터 시작해서 A[1]까지 연속된 두 원소를 교환해서 이동해야 합니다.

 

swap(A[4], A[3]);

swap(A[3], A[2]);

swap(A[2], A[1]);

 

이제 A[1]까지의 원소는 정렬이 완료되었으니깐 다음은 A[2] 원소를 기준으로 위 과정을 반복하면 정렬이 완료됩니다.

 

그런데 문제에서 "교환은 많아봐야 S번 할 수 있다."라는 조건이 있으니깐 A[i]에서 현재 남아있는 S번의 횟수로 A[i + 1] , A[i + 2] , ... A[i + s] 중에서 A[i]보다 큰 최댓값을 찾을 수 있는지를 판별해야 합니다.

 

예를 들면 아래와 같은 배열이 있고 S=2라고 했을 때

 

index 0 1 2 3 4

value 7 1 2 3 4

  

A[1]에서 현재 남아있는 2번의 횟수로 A[2], A[3] 중에서 A[i]보다 큰 최댓값은 A[3]이 됩니다.

 

swap(A[3], A[2]);

swap(A[2], A[1]);

 

index 0 1 2 3 4

value 7 3 1 2 4

 

아래는 위 알고리즘을 구현한 코드입니다.

 

<C++소스코드>

#include <iostream>
#include<algorithm>
using namespace std;
 
int n, s;
int A[50];
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    cin >> s;
 
    for (int i = 0; i < n; i++) { //각각의 A[i]에 대해서
        int maxValue = 0;
        int maxIndex = 0;
        int curIndex = i + 1;
        for (int j = 0; j < s; j++) { // 남아있는 S만큼의 횟수로 A[i + 1], A[i + 2], ... A[i + s]의 원소의 최댓값을 찾아서
            if (curIndex >= n) break;
            if (A[curIndex] > maxValue) {
                maxValue = A[curIndex];
                maxIndex = curIndex;
            }
            curIndex++;
        }
        if (A[i] < maxValue) { // 만약에 A[i] 보다 큰 값을 찾았다면
            for (int j = maxIndex; j > i; j--) { // A[i]의 위치까지 swap하면서 옮겨준다.
                swap(A[j], A[j - 1]);
                s--;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << A[i] << ' ';
    }
}