[백준] 정렬 알고리즘 - 1083. 소트

문제

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

 

입력

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

 

출력

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

 

예제 입력1

7

10 20 30 40 50 60 70

1

 

예제 출력1

20 10 30 40 50 60 70

 

예제 입력2

5
3 5 1 2 4
2

 

예제 출력2

5 3 2 1 4

 

예제 입력3

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

 

예제 출력3

20 19 18 17 16 15 14 13 12 11

 

생각

맨 처음에 문제를 풀어서 예제 입출력을 비교해보니 맞길래 내가 생각하고 있던 게 맞다라고 생각했다. 

처음에 생각했던 거는 인덱스를 0부터 시작해서 다음 인덱스와 비교해가면서 자리를 바꾸는 것이었다. 

테스트 케이스를 넣었을 때 답이 잘 나오길래 제출했더니 틀렸다는 결과가 나왔다. 

 

뭐가 잘못됐나 싶어서 검색해보니 입력 어쩌구 저쩌구 사전식 어쩌구 저쩌구 여러 질문글이 많았다.

예제 케이스가 3개니깐  while(~scanf("%d", &n)) 써서 입력을 받아야된다... 하길래 수정해서 제출했더니 이번에는 출력 초과. 출력 초과 출력이 너무 많다는 건데 암튼 그래서 이해를 못했다. 

 

+) 처음의 접근(오답)

#include <iostream>
using namespace std;


int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n,s;
    
    while(~scanf("%d", &n)){
    
        int arr[n];
        for(int i=0; i<n; i++){
            cin >> arr[i];
        }
        
        cin >> s;
        int temp;
        while(s-->0){
            for(int i=0; i<n-1; i++){
                if(arr[i] < arr[i+1]){
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                    
                    break;
                }
            }
        }
        for(int j=0; j<n; j++){
           cout << arr[j] << " ";
        }
    }
    return 0;
}

맞은 분 풀이와 설명을 듣고 문제를 아예 잘 못 이해하고 있었구나 싶었다. 예제 입력들이 좀 더 다양했으면 좋았을 텐데 나뿐만 아니라 다른 분들도 문제가 잘 이해가 안된다고 했다. 

 

추가적으로 예시를 들어 문제 이해를 다시해보자.

예를 들면, 

6

10 20 30 40 70 60 

5

 

1번째) 10 20 30 70 50 60 

2번째) 10 20 70 30 50 60 

3번째) 10 70 20 30 50 60 

4번째) 70 10 20 30 40 60

5번째) 70 20 10 30 40 60   --> 결과 출력 

 

이런 식으로 과정이 전개된다. 

 

 

이제 아래의 코드를 설명하자면,

newSort() : 새로운 정렬을 정의하는 함수이다. 

l : 인덱스 값을 저장하기 위한 변수이다.

max : 가장 큰 값을 저장하기 위한 변수이다.

 

newSort()라는 함수를 정의하는데, newSort()안의 첫번째 for 문에서 j <= j+s 로 하는 이유는 s번까지 교환 할 수 있기 때문이다. 즉, s번 안에 원소의 교환을 완료해야되기 때문이다. 그리하여 max값을 찾고 그 때의 인덱스 j의 값을 l에 저장한다. 만약 l이 i와 같지 않으면, for문을 돌면서 원소를 한칸씩 밀어준다. 그리고 i번째에는 max값을 넣는다. 반복한 횟수(l-i) 만큼 s에서 빼주고 이를 반복한다. s가 0이면 빠져나온다. 

 

 

 

작성한 코드

#include<iostream>

using namespace std;

int a[50];
int n, s;

void newSort() {
   for (int i = 0;i < n;i++) {
      int max = a[i];  // 가장 큰 값을 저장하기 위한 변수
      int l = i;	   // 가장 큰 값일 때, 그 때의 인덱스 값을 저장하기 위한 변수 
      for (int j = i+1; j <= i + s; j++) {  
         if (j == n) break;	
         if (max < a[j]) {
            max = a[j];
            l = j;
         }
      }
      if (l != i) {
         for (int k = l; k > i; k--) { // 한 칸씩 밀어준다.
            a[k] = a[k - 1];
         }
         a[i] = max;
         s -= (l - i);
      }

      if (s == 0) break;
   }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    
    for (int i = 0;i < n;i++){
        cin >> a[i];
    }
    cin >> s;
     
    newSort();

    for (int i = 0;i < n;i++){
        cout << a[i] << ' ';
    }
    return 0;
}