[백준] 정렬 - 2947. 나무 조각

문제

동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다.

동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다.

1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.

 

출력

두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.

 

예제 입력1

2 1 5 3 4

 

예제 출력1

1 2 5 3 4
1 2 3 5 4
1 2 3 4 5

 

생각

5. 만약 순서가 1,2,3,4,5 순서가 아니라면 다시 1단계로 돌아간다는 조건때문에 check함수를 두어 정렬이 완성되지 않았으면 계속하게끔 코드를 작성하였다. 

(i, j)  0, 1/ 1, 2/ 2, 3 / 3, 4/ 4, 5/  

 

 

제출하고 나서 다른 풀이를 보니깐 굳이 check함수를 두어서 while문을 돌지 않아도 되는 거였다!

for(int i=0; i<5; i++){
	for(int j=0; j<4-i; j++){
    	if(arr[j] > arr[j+1]){
        	int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            
            printf("%d %d %d %d %d\n", arr[0], arr[1], arr[2], arr[3], arr[4]);
        }
    }
}

※ 버블정렬(Bubble Sort)

: 두 인접한 원소를 검사하여 정렬하는 방법. 시간 복잡도는 O(N^2)이다. 

 

 

작성한 코드

#include <iostream>
using namespace std;

int arr[5];
int check(){
    for(int i=0; i<5; i++){
        if(arr[i] != i+1){
            return -1;
        }
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
   
    int temp;
    
    for(int i=0; i<5; i++){
        cin >> arr[i];
    }
    
    while(check()==-1){
        for(int i=0; i<4; i++){
            for(int j=i+1; j<i+2; j++){
                if(arr[i] > arr[j]){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    
                    for(int i=0; i<5; i++){
                        cout << arr[i] << " ";
                    }
                    cout << "\n";
                }
                else{
                    continue;
                }
            }
        }
    }
    return 0;
}