[백준] 2947번 : 나무 조각 - C/C++

문제를 읽고 어떻게 접근해야할지 생각했는데

생각보다 간단했다.

 

입력을 받고, 첫 번째와 두 번째 수를 비교하고 그 다음 수를 비교하고..

근데 문제가 생겼다.

 

동작이 잘 될 줄 알고

if문으로 구현했는데 한 번씩만 인접한 배열을 비교하는 것이었다.

 

결국 출력은 아래처럼.. 나오게 된다.

틀렸다는 뜻.

 

간단하다고 말했던 걸 후회한다.

나는 풀이과정을 다시 생각해야했다..

 

많은 고민을 하다가 if문이 아닌 다른 방법이 있을까.. 했는데

bubble sort(버블 정렬)이 생각났다.

 

버블 정렬로 풀어보자.

버블 정렬의 핵심은 다음과 같다.

 

버블 정렬은 인접한 두 개의 원소를 비교하여, 마지막 원소까지 늘려가며 정렬하는 알고리즘이다.

 

알고리즘은 아래의 4단계를 거쳐 실행된다.

 

1. 첫 번째 원소와 두 번째 원소 비교

2. 첫 번째 원소가 더 작은 경우, 두 원소 swap(교환)

3. 1~2단계를 반복하며 마지막 원소까지 비교

(1~3단계를 거치면 마지막 원소가 가장 큰 값이 되어있음)

여기서 핵심!

1~3 단계 작업을 하고 정렬을 중단하는 것이 아닌,

4. 마지막 원소를 제외하고 1~3단계를 반복

 

위의 단계를 코드로 적용해보자.

 

 

 

나무 조각은 5개가 고정되어있으니, 고정된 크기의 배열 입력

int ary[5];
 
for (int i = 0; i < 5; i++) {
	cin >> ary[i];
}

 

boolean 함수를 사용해야한다.

배열이 되어있지 않다는 것으로 초기화해두자.

bool sorted = false;

 

 

while문을 돌아야하는데... 어떻게 돌아야할까.

아래처럼 코드를 작성할 수 있다.

while (!sorted) {
    sorted = true;

    for (int i = 0; i < 4; i++) {
      	if (ary[i] > ary[i + 1]) {
            swap(ary[i], ary[i + 1]);
            sorted = false;
...

왜 i의 범위가 0~5가 아니라, 0~4일까.

마지막 원소는 가장 큰 것으로 정렬되어있다고 가정하고 진행하기 때문이다.

 

마지막 원소를 제외하고 두 개의 원소를 비교하자.

참이라면, swap 해주기.

 

swap이 실행되었다면,

swap된 결과값 출력하기

for (int j = 0; j < 5; j++) {
    cout << ary[j] << " ";
}

 

이런식으로.. 코드를 작성할 수 있다.

아주 멋지게 문제에서 주어진 예제 입/출력이 동작한다.

 

 

 

 

 

전체 코드

#include <iostream>

//나무 조각
using namespace std;

int main(){
    int ary[5];
 
	for (int i = 0; i < 5; i++) {
		cin >> ary[i];
	}
 
	bool sorted = false;
    while (!sorted) {
        sorted = true;

        for (int i = 0; i < 4; i++) {  //마지막 원소가 가장 크다고 가정
            if (ary[i] > ary[i + 1]) {  //원소 두 개 비교
                swap(ary[i], ary[i + 1]);  //swap
                sorted = false;

                //swap하면 실행
                for (int j = 0; j < 5; j++) {
                    cout << ary[j] << " ";
                }
                cout << "\n";
            }
        }
    }
	return 0;
}

 

 

 

 

 

 

브론즈1 문제였다.

역시.. 간단하지만은 않았던 것 같다.

'이런식으로 동작하겠지' 정도로 공부하면 안 될 것 같다.

확실하게 알고리즘 공부를 해서 효율적으로 코드를 작성하고 싶다.

 

 

 

 

ps.) 코드를 작성할 때, if문이나 for문을 작성할 때 띄어쓰기를 잘 안하는데..

업로드를 하고 보니까 가독성이 조금(?) 떨어지는 것 같다.

업로드할 때 최대한 가독성 좋게..

코드를 수정해서 올려보도록 노력해야겠다.

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️