백준 / 1083 / 소트 / C++

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    int s;
    cin >> s;
    int maxidx = 0;
    while (1)
    {
        bool swapcheck = false;
        int curmaxval = 0;
        int curmaxvalidx;
        for (int i = 0; i < n - 1; i++)
        {
            if (arr[i + 1] > arr[i])
            {
                swapcheck = true;
            }
        }
        if (!swapcheck)
        {
            for (auto i : arr)
            {
                cout << i << " ";
            }
            return 0;
        }
        for (int i = maxidx, j = s; i < n && j >= 0; i++,j--)
        {
            if (curmaxval < arr[i])
            {
                curmaxval = arr[i];
                curmaxvalidx = i;
            }
        }
        if(curmaxvalidx - maxidx <= s)
        {
            for (int i = curmaxvalidx; i > maxidx; i--)
            {
                swap(arr[i], arr[i - 1]);
            }
            s -= curmaxvalidx - maxidx;
            maxidx++;
        }
        else
        {
            while (s--)
            {
                swap(arr[curmaxvalidx], arr[curmaxvalidx - 1]);
                curmaxvalidx--;
            }
            for (auto i : arr)
            {
                cout << i << " ";
            }
            return 0;
        }
        if (!s)
        {
            for (auto i : arr)
            {
                cout << i << " ";
            }
            return 0;
        }
    }

    /*while (1)
    {
        bool swapcheck = false;
        if (!s)
        {
            for (auto i : arr)
            {
                cout << i << " ";
            }
            return 0;
        }
        for (int i = 0; i < n - 1; i++)
        {
            if (arr[i + 1] > arr[i])
            {
                swapcheck = true;
                swap(arr[i + 1], arr[i]);
                s--;
                break;
            }
        }
        if (!swapcheck)
        {
            for (auto i : arr)
            {
                cout << i << " ";
            }
            return 0;
        }
    }*/
    return 0;
}

많이 틀렸다... 시행착오가 엄청났다

제일 처음에는 그냥 주석처리했던 버블소트에서 교환 횟수를 세고, 주어진 횟수가 된다면 break 후 출력... 이라고만 생각했지만 아니었다. 이러면 사전순 배열이 아닌, 단순히 횟수만큼의 버블소팅을 하는 알고리즘이었고, 결과는 당연히 틀렸습니다.

그 이후에 생각한 알고리즘은 배열에서 제일 큰 값을 maxidx(0으로 초기화) 인덱스로 옮겨오는데, 거기에 사용되는 횟수(큰값 인덱스 - maxidx)가 s 이하라면 그렇게 실행하고 아니라면 원래 작성했던 알고리즘을 사용했지만... 실패

최종적으로 생각한 것은 배열에서 제일 큰 값을 그냥 맨 앞쪽으로, 그리고 그 다음 큰 값을 그 다음 인덱스로 가져오되, 횟수를 차감하는 단순한 알고리즘이지만 만약 남아있는 S의 값으로 남은 배열의 나머지 부분을 전부 탐색할 수 없다면 maxidx ~ maxidx + s까지의 값들 중 제일 큰 값을 maxidx로 옮겨오도록 했다. 그리고 swapcheck를 통해 불필요한 스왑 과정이 필요없다면 바로 cout 후 return.