[BOJ] 1083_소트

소트

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

1083번: 소트

성공

 

버블소트를 응용하여 배열을 정렬한다.
'소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.'
즉, 크기가 큰 순서대로 정렬하다가 s번 정렬 했을 시 해당 순서를 출력하라는 의미이다.

 

• 정답 코드

    #include<iostream>
    using namespace std;
  
    #define maxNum 51
  
    int n, s;
    int list[maxNum];
  
    void sorting() {
        for (int i = 0; i < n && s; i++) {
            int max = list[i], maxIdx = i;
            int  count = min(n, i + 1 + s);
  
            for (int k = i+1; k < count && s; k++) {
                if (max < list[k]) {
                    if (max < list[k]){
                        max = list[k];
                        maxIdx = k;
                    }
                }
            }
            s -= maxIdx - i;
  
            for (int k = maxIdx; k > i; k--)
                list[k] = list[k - 1];
  
            list[i] = max;
        }
    }
  
    int main() {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> list[i];
        cin >> s;
  
        sorting();
  
        for (int i = 0; i < n; i++)
            cout << list[i] << ' ';
  
        return 0;
    }