백준 2947번 [나무 조각](C++) -yes6686- 티스토리

백준 문제 풀이: 2947 (나무 조각)

---

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

문제 설명:

다섯 개의 나무 조각이 주어지며, 초기 상태에서 나무 조각들을 정렬합니다. 인접한 두 조각의 순서가 잘못된 경우, 이를 교환하며 정렬 과정을 출력해야 합니다. 최종적으로 오름차순으로 정렬될 때까지 과정을 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[6]; // 나무 조각 배열 (인덱스 0~4 사용)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 입력 받기
    for (int i = 0; i < 5; i++) {
        cin >> arr[i];
    }

    // 정렬 과정
    while (true) {
        bool swapped = false; // 교환이 발생했는지 확인하기 위한 플래그

        for (int i = 0; i < 4; i++) {
            if (arr[i] > arr[i + 1]) {
                // 인접한 두 수를 교환
                swap(arr[i], arr[i + 1]);
                swapped = true;

                // 현재 배열 상태 출력
                for (int t = 0; t < 5; t++) {
                    cout << arr[t] << ' ';
                }
                cout << '\n';
            }
        }

        // 더 이상 교환이 발생하지 않으면 종료
        if (!swapped) {
            break;
        }
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 버블 정렬의 개념 적용: - 인접한 두 수를 비교하여, 순서가 잘못된 경우 교환합니다.
• 과정 출력: - 교환이 발생할 때마다 배열 상태를 출력합니다.
• 종료 조건: - 더 이상 교환이 발생하지 않으면 정렬이 완료된 상태이므로 반복을 종료합니다.

세부 구현:

• swap(arr[i], arr[i + 1]): 인접한 두 값을 교환합니다.
• swapped: 교환이 발생했는지를 확인하는 플래그입니다.

시간 복잡도 분석

• 버블 정렬의 시간 복잡도는 최악의 경우 O(n²)입니다.
• 배열의 길이가 항상 5로 고정되어 있으므로, 연산량은 매우 작습니다.

---

결과

나무 조각을 정렬하면서 교환이 발생할 때마다 배열 상태를 출력합니다.

• 입력 예시:

  2 1 5 3 4

• 출력 예시:

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

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!