[파이썬/Python] 백준 2947번: 나무 조각

📌 문제 : 백준 2947번

---

📌 문제 탐색하기

nums : 나무 조각에 쓰인 숫자 리스트

✅ 입력 조건
1. 5개의 나무 조각에 쓰여진 숫자 입력
✅ 출력 조건
1. 숫자들이 [1, 2, 3, 4, 5]가 되는 과정 출력

문제에 제시된 것처럼 구현한다.
1. 1번째 & 2번째 비교, 필요 시 위치 변환
2. 2번째 & 3번째 비교, 필요 시 위치 변환
3. 3번째 & 4번째 비교, 필요 시 위치 변환
4. 4번째 & 5번째 비교, 필요 시 위치 변환
5. 원하는 배열의 리스트가 아니면 위의 과정 반복 수행

즉, 버블 정렬(bubble sort)를 직접 구현해보는 문제이다.

가능한 시간복잡도

N개 입력받기 → $O(N)$
버블 정렬 → $O(N^2)$
리스트를 원하는 형태로 출력 → $O(N)$

최종 시간복잡도
$O(N^2*N) = O(N^3)$이고 N은 5로 고정되어있으므로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

while문의 조건에 부합할 때까지 for문을 돌면서 요소 위치 변경.

---

📌 코드 설계하기

1. nums 입력
2. while문으로 종료조건(원하는 배열 리스트가 될 때) 작성
3. 리스트 요소 확인해 배열 위치 조정
   
   

---

📌 정답 코드

import sys

input = sys.stdin.readline

# 0. 필요 변수 선언
want = [1, 2, 3, 4, 5]

# 1. `nums` 입력
nums = list(map(int, input().split()))

# 2. while문으로 종료조건(원하는 배열 리스트가 될 때) 작성
while True:
    if nums == want:
        break

    # 3. 리스트 요소 확인해 배열 위치 조정
    for i in range(1, 5):
        if nums[i-1] > nums[i]:
            nums[i-1], nums[i] = nums[i], nums[i-1]
            print(' '.join(map(str, nums)))		# 또는 print(*nums)

• 결과
  

---

📌 회고

• 이 문제를 봤을 때, 버블 정렬을 구현하는 문제인지 바로 알아봤어야 했는데 그러지 못했다. 알고리즘을 정리하는 시간을 가져야겠다.