백준 1083번 소트 - C++ 풀이

---

 

1. 그리디 하게 앞자리부터 큰 수로 만들어야 한다.
2. i번째 자리에서 X칸 떨어져있는 수는 X번의 스왑으로 i번째 자리로 끌어올 수 있다.
3. S번 이내의 스왑으로 끌어올 수 있는 가장 큰 수를 앞으로 끌어오기를 반복한다.

 

1. 그리디하게 앞자리부터 큰 수로 만들어야 한다.

 결과가 사전 순으로 가장 뒷서도록 하려면 최대한 앞을 큰 수로 만들어야 한다.

 

2.  i번째 자리에서 X칸 떨어져 있는 수는 X번의 스왑으로 i번째 자리로 끌어올 수 있다.

 그리고 i번째 자리(A[i])에서 X칸 떨어져 있는 수(A[i+X])는 최소 X번의 스왑으로 i번째 자리로 끌어올 수 있다. A[i+X]를 A[i+X-1], A[i+X-2], ... 순으로 스왑하면 총 X번의 스왑으로 A[i+X]를 A[i]자리로 끌어오고, A[i+1]~A[i+X-1]은 뒤로 한 칸씩 밀리도록 할 수 있다.

 

3. S번 이내의 스왑으로 끌어올 수 있는 가장 큰 수를 앞으로 끌어오기를 반복한다.

 1, 2번 사실을 이용해서 남은 S번 이내의 스왑으로 끌어올 수 있는 가장 큰 수, 즉 [현재 위치] ~ [현재 위치+S]에서 가장 큰 수를 찾고, 그 수를 현재 위치로 끌어오는 과정을 반복한다.

반응형

---

#include <iostream>

using namespace std;

int N, S;
int A[51];

int main()
{
    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i];
    cin >> S;
    
    int start = 0;
    while (start < N && S > 0) {
        // S번 이내의 스왑으로 끌어올 수 있는 가장 큰 값을 A[start]로 끌어오기
        int maxIdx = start;
        
        for (int i=start; i<=min(N-1, start+S); i++) {
            if (A[maxIdx] < A[i]) maxIdx = i;
        }
        for (int i=maxIdx; i>start; i--) {
            swap(A[i], A[i-1]);
            S--;
        }
        
        start++;
    }
    
    for (int i=0; i<N; i++) cout << A[i] << " ";

    return 0;
}