오늘은 구현 유형인 백준 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
'개발공부 > BAEKJOON' 카테고리의 다른 글
[백준 / python] 2578번 빙고 (0) | 2024.08.12 |
---|---|
[백준 / python] 7568번 덩치 (0) | 2024.08.11 |
[백준 / python] 25305번 커트라인 (0) | 2024.08.09 |
[백준 / python] 5635번 생일 (0) | 2024.08.08 |
[백준 / python] 1181번 단어 정렬 (0) | 2024.08.07 |