소트 (백준 1083)

안녕하세요. 오늘은 정렬을 할 거예요.

문제

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

아이디어

자신의 인덱스를 idx라고 합시다.
그리고 현재 남은 S값을 가지고 연산을 할 겁니다.

arr[idx]부터 arr[idx+S]까지중 최댓값의 위치를 j라고 합시다. 그러면 S에서는 j-idx만큼을 빼주어야하고 j에 있던 값을 swap해서 i까지 끌면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, arr[55] = { 0 }, S, i, j;
    cin >> N;
    for (i = 1; i <= N; i++) cin >> arr[i];
    cin >> S;

    for (i = 1; i <= N; i++)
    {
        ll mx = 0, p = i;
        for (j = i; j <= min(N, i + S); j++)
        {
            if (mx < arr[j])
            {
                mx = arr[j];
                p = j;
            }
        }
        S -= p - i;

        for (j = p - 1; j >= i; j--) swap(arr[j], arr[j + 1]);
    }

    for (i = 1; i <= N; i++) cout << arr[i] << ' ';
}

감사합니다.