백준 1083번 "소트"

백준 1083번 “소트”

Question:

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

Input:

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

Output:

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

Restriction:

시간제한:
2 초

Example Case:

Input case 1:

7
10 20 30 40 50 60 70
1

Output case 1:

20 10 30 40 50 60 70

Input case 2:

5
3 5 1 2 4
2

Output case 2:

5 3 2 1 4

Input case 3:

10
19 20 17 18 15 16 13 14 11 12
5

Output case 3:

20 19 18 17 16 15 14 13 12 11

풀이 과정:
이 문제는 버블 정렬을 활용한 문제이다.

버블 정렬이란,
연속한 두 원소의 우선순위를 비교하여 교환하면서 정렬하는 방법이다.

이 문제의 조건으로 “사전순으로 가장 뒷서는 순서”는,
배열의 앞자리일수록 데이터 정수 기준 가장 큰값이 오면 된다.

문제를 처음 접했을 때,
버블 정렬만 구현하면 되는 줄 알고 구현하였다가
엄청나게 틀렸다.

이 문제의 핵심은 “사전순으로 가장 뒷서는ㅡ” 이라는 문구인데,
생각해보면 순차적으로 우선순위에 맞게 정렬하여 배열 뒷자리부터 정렬이 되는 버블 정렬의 성질에서,
배열 안에서의 최대값을 최대한 배열의 앞자리로 두개씩 교환하여 가져와야한다.
그런데, 이 부분에서 이동할 수 있는 횟수는 제한되어 있고,
따라서,이중 for문에서의 범위 내에서 이동횟수 안으로 최대값을 가져올 수 있는지 생각해봐야한다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n,s;
    cin >> n;
    int *arr = new int[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; //최댓값의 index
        for(int j = i+1;j<n;j++) { //이중 for문, i+1부터 시작(i 다음 원소부터)
            if(s-(j-i) >= 0) { //남아있는 이동 횟수가 존재한다면,
                if(max < arr[j]) { // 그 범위안에서 최댓값과 그 인덱스를 찾아오자
                    max = arr[j];
                    maxi = j;
                }
            }
        }
        for(int j = maxi;j>i;j--) { //찾아왔다면,최대값을 가지고 있는 index부터,
            swap(arr[j],arr[j-1]); //최대값을 옮길수 있는 횟수 내에서 가져오고 나머지 데이터 밀어내기(2개씩 교환)
            // ex. 1 2 3 4 (s > 4) => 4 = max, 4 3 / 4 2 / 4 1 교환하여 4 1 2 3 형성
            // 4 3 2 1 ...
        }
        s -= (maxi - i); // 옮긴 횟수 갱신
        if(s <= 0) { // 옮길수 있는 횟수가 없다면 종료
            break;
        }
    }

    for(int i = 0;i<n;i++) {
        cout << arr[i] << " ";
    } // answer
    delete[] arr;
}

• 백준
• 문제풀이
• 알고리즘