[백준] 1083번 소트 - C++

https://www.acmicpc.net/problem/1083

1083번: 소트

문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

---

        '사전 순으로 가장 뒷서는 것'이라는 것에 대해 생각하고 풀어야 하는 문제이다. 이말인 즉슨 결국 가장 큰 숫자를 최대한 앞으로 당겨와야한다는 의미이다. S가 허용하는 한 최대한 뒤로 간 다음에 가장 큰 숫자를 당겨오는 방식을 사용하고 swap이 일어난 횟수 만큼 S에서 차감해주면 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int N,S,temp, cnt = 0, maxnum,maxidx;
int arr[51];

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    cin >> S;

    for(int i = 0; i < N - 1 && S != 0; i++){
        cnt = 0;
        maxnum = arr[i];
        maxidx = i;
        for(int j = i + 1; j < N && cnt < S;j++,cnt++){
            if(maxnum < arr[j]){
                maxnum = arr[j];
                maxidx = j;
            }
        }
        int j = maxidx;
        if(maxidx > i){
            while(j != i){
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j-- ;
            }
        }
        S -= (maxidx - i);
    }   
    for(int i = 0; i < N; i++){
        cout << arr[i] << " ";
    }
    return (0);
}

---

    처음에는 버블소트를 하면서 swap이 일어난다면 S만큼 swap이 일어난다면 배열을 출력하는 방법을 사용하였다. 그랬더니 예제는 잘 나왔지만 잘 되지 않는다는 것을 확인하였다. 조금 더 생각을 해보니 처음부터 옮기면 되지 않을까 싶었다. 하지만 사전 순으로 뒷선 다는 것은 그런 것이 아니었다. 앞에 것을 아무리 먼저 바꿔도 뒤에 있는 것 하나를 가져오는 것이 사전 순으로는 뒤에 있는 것이었다. 오랜만에 코딩을 해서 그런지 잘 되지 않았다. 다시 재활 치료를 해야되겠다!!

    한달동안 42서울 라 피신에 참여하느라 백준 문제를 풀지 못했다. 하지만 재미있는 한달을 보낸 것 같아 후회는 안된다. 라 피신에 대한 내용을 추가적으로 포스팅을 올려야겠다!