[백준 / python] 2947번 나무 조각

오늘은 구현 유형인 백준 2947번 문제, 나무 조각을 풀어보겠습니다!

 

< 문제 확인 >

https://www.acmicpc.net/problem/2947

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다.

동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다.

---

첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

---

 

먼저, 이 문제는 주어진 5개의 나무 조각을 1, 2, 3, 4, 5 순서로 정렬해야하는 문제입니다!

정렬을 진행하는 과정에서 두 조각의 위치가 바뀔 때마다 그 중간 과정을 출력합니다.

주어진 나무 조각들은 항상 1부터 5까지의 숫자이며, 중복되지 않습니다.

 

정렬 방식은 버블 정렬 방식을 사용하여 인접한 두 숫자를 비교하고,

자리를 바꿔가면서 오름차순으로 정렬합니다.

매번 자리를 바꿀 때마다 리스트의 상태를 출력하여 정답을 구하면 됩니다!

 

✔️ 가능한 시간복잡도

버블 정렬은 최악의 경우 O(n^2) 시간복잡도를 가집니다.

이 문제에서는 5개의 숫자를 정렬하는 것이므로, 최대 25번의 비교와 교환이 필요하고

충분히 제한 시간 내에 해결이 가능합니다.

 

✔️ 알고리즘

초기 상태를 입력받아 리스트에 저장하고 버블 정렬 방식을 이용해 중간 과정을 출력한다!!

 

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 초기 상태를 입력받고 리스트에 저장합니다.

2. 버블 정렬을 활용하여 인접한 두 숫자를 비교하고 필요 시 자리를 바꿉니다.

3. 자리가 바뀔 때마다 해당 리스트의 상태를 출력합니다.

4. 최종적으로 1, 2, 3, 4, 5로 정렬된 상태가 될 때까지 중간 과정이 모두 출력됩니다.

---

📌 시도 회차 수정 사항 (Optional)

무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

---

📌 정답 코드

# 나무 조각의 초기 순서 입력
wood_pieces = list(map(int, input().split()))

# 버블 정렬을 수행하며 매 교환마다 상태 출력
while (wood_pieces != [1, 2, 3, 4, 5]):
    for i in range(4):
        if (wood_pieces[i] > wood_pieces[i + 1]):
            wood_pieces[i], wood_pieces[i + 1] = wood_pieces[i + 1], wood_pieces[i] # 자리 바꾸기
            print(" ".join(map(str, wood_pieces)))

주말에도 챌린지는 계속됩니다! 구현 유형도 차근차근 마스터하고 싶어요 ㅎㅎ

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no