[백준 1083번] 소트 (C++)

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

1083번: 소트

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, S;
int arr[51];

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

    for(int i=0; i<N; i++)
    {
        int max = arr[i];
        int maxi = i;
        for(int j= i+1; j<min(N, i+S+1); j++) //N or S범위내까지
        {
            if(max < arr[j]) //범위내 가장 큰 값 및 인덱스 저장
            {
                max = arr[j];
                maxi = j;
            }
        }

        for(int j=maxi; j>i; j--) //가장 큰 값 인덱스 기준으로 swap
        {
            swap(arr[j], arr[j-1]);
            S--; //매 swap 마다 카운트 감소
        }
    }

    for(int i=0; i<N; i++)
    {
        cout << arr[i] << " ";
    }
}

 

처음에 단순 버블정렬 문제로 이해하고 풀었다가 상당히 고민했던 문제이다.

주어진 S 범위 내에 가장 큰 값을 위로 끌어올리는 것을 반복하는 문제였다.

 

먼저 처음에 비교 대상으로 삼을 max, maxi(인덱스) 값을 초기화해놓고 그 다음값 ~ S 범위내에 가장 큰 값을 확인하여 max와 maxi를 갱신한다.

해당 내용이 수행되는 반복문에서 min(N, i+S+1)을 해주었는데 j이 이 둘 모두보다 작아야하기 때문에 더 작은 값을 선택하도록 해주었다. (N범위 이내 or 현재 i 기준 S 범위 이내)

 

이후 갱신했던 maxi를 기준으로 위로 swap을 해주며, 매 swap 마다 교환횟수가 차감되므로 S또한 감소시켜준다.

위를 반복하여 정렬을 마치고 정렬된 배열을 출력해주면 된다.

 

5
3 5 1 2 4
2

i = 0 / 3 기준
탐색 가능 범위 : 3 5 1
범위내 최대값 : 5
범위내 최대값 인덱스 : 1
정렬후 : 5 3 1 2 4(swap 1회 발생) (S=1)

i = 1 / 3 기준
탐색 가능 범위 : 3 1
범위내 최대값 : 3 (현위치 동일 이후 패스)
정렬후 : 5 3 1 2 4

i = 2 / 1 기준
탐색 가능 범위 : 1 2
범위내 최대값 : 2
범위내 최대값 인덱스 : 3
정렬후 : 5 3 2 1 4 (swap 1회 발생) (S=0)

S=0 이므로 정렬 종료
결과값 : 5 3 2 1 4