BOJ 2947 - 나무 조각

문제

1부터 5까지 적힌 나무 조각 5개가 임의 순서로 있다. 버블 정렬로 오름차순 정렬하되, 인접 원소를 교환할 때마다 현재 배열 상태를 출력하라.

입력

5개의 나무 조각 순서가 주어진다.

출력

교환이 발생할 때마다 전체 배열을 한 줄에 출력한다.

예제

입력	출력
`2 1 5 3 4`	`1 2 5 3 4` `1 2 3 5 4` `1 2 3 4 5`

풀이

5개 원소에 대해 버블 정렬을 수행하며 교환 시마다 배열을 출력한다.

바깥 반복문을 5부터 1까지 역순으로 진행한다 (정렬된 영역 확장)
안쪽 반복문으로 인접 원소를 비교하여 앞이 더 크면 교환한다
교환이 발생하면 전체 배열을 출력한다
정렬이 완료될 때까지 반복한다

핵심 아이디어: 고정 크기 5인 배열의 버블 정렬이므로 시간 복잡도는 O(1)이며, 교환 이벤트를 출력으로 추적한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int p[6];
 
int main()
{
  for (int i = 1; i <= 5; i++)
    cin >> p[i];
 
  for (int i = 5; i >= 1; i--)
  {
    for (int j = 1; j < i; j++)
    {
      if (p[j] > p[j + 1])
      {
        swap(p[j], p[j + 1]);
        for (int k = 1; k <= 5; k++)
          cout << p[k] << " ";
        cout << endl;
      }
    }
  }
}

복잡도

시간: O(1) (고정 크기 5)
공간: O(1)

문제