[백준] 2947번 - 나무 조각 (파이썬)

https://www.acmicpc.net/problem/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가 아니다.

출력

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

문제 탐색하기

두 숫자를 서로 비교하면서 최종적으로 오름차순으로 정렬되도록 해야 한다.

하지만 결과만이 아니라 중간 과정도 함께 보여줘야 하기 때문에 루프 안에서 비교할때마다 같이 출력을 해줘야 한다.

알고리즘은 버블 정렬을 이용하여 구현해보았다.

 

배열의 크기가 N이라면 N-1개의 원소와 비교하게 된다. 최악의 경우에는 모든 원소를 교환해야 하며, 이로 인해 버블 정렬의 시간 복잡도는 O(N^2)가 된다. 이번 문제에서는 원소가 5개이기 때문에 최악의 경우 약 25번의 연산이 발생하게 된다.

코드 설계하기

처음에 원소들의 순서를 입력받아 이를 리스트에 저장한다. 리스트의 앞부분부터 두 개씩 비교해 더 큰 값이 앞에 있을 경우 자리를 바꾼다. 이 과정을 리스트 끝까지 반복하며, 순서가 바뀔 때마다 그 결과를 출력한다. 한 번의 순환이 끝나면 가장 큰 값이 맨 끝에 정렬되고, 그 이후부터는 해당 값은 비교에서 제외된다. 따라서 남은 원소들 간의 비교는 한 단계씩 줄어들게 된다.

 

코드

import sys
input = sys.stdin.readline()

num = list(map(int, input.split()))

for i in range(len(num) - 1):
  for j in range(0, len(num) - (i + 1)):
    if (num[j] > num[j + 1]):
        num[j], num[j + 1] = num[j + 1], num[j]
        print(*num)