파이썬 Python | 알고리즘 | 백준 나무 조각

⭕ 파이썬 Python | 알고리즘 | 백준 나무 조각

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• 1부터 5까지의 숫자가 적힌 나무 조각을 1, 2, 3, 4, 5 순서로 정렬해야 한다. 인접한 두 조각만 바꿀 수 있고, 바뀔 때마다 현재 순서를 출력해야 한다.
• 버블 정렬을 직접 구현하는 문제라고 생각한다. 버블 정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘으로, 시간 복잡도는 O(n^2)이다. 하지만, 항상 5개의 조각만 다루고, 각 단계를 출력해야 하는 요구사항 때문에 버블 정렬이 오히려 적합하다고 생각한다.

(N-1) + (N-2) + ... + (2) + (1) = N(N-1)/2

• 단순 구현 문제는 시간복잡도를 계산할 만큼 빡빡하게 나오는 일이 별로 없다고 한다!

 

➡️ 코드 설계하기

• sys.stdin.readline()을 사용하여 한 줄로 입력받고, map과 list를 사용해 정수 리스트로 변환한다.
• while 루프를 사용해 리스트가 [1, 2, 3, 4, 5]가 될 때까지 반복한다.
  
  • for 루프를 사용하여 리스트의 앞에서부터 두 개씩 비교한다.
  • if 조건문으로 앞의 값이 더 크면 두 값의 위치를 교환한다.
  • 교환이 발생할 때마다 현재 상태를 출력한다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회 차

• 1 2 5 3 4 형태로 출력되어야 하는데 [1, 2, 5, 3, 4] 같은 출력형태가 된다. 문제에서 요구하는 출력 형식을 맞추기 위해 수정이 필요하다.

import sys

numbers = list(map(int, sys.stdin.readline().strip().split()))

while numbers != [1, 2, 3, 4, 5]:
    for i in range(4):
        if numbers[i] > numbers[i + 1]:
            numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
            print(numbers)

---

2회 차

• 시간 108ms
• map과 join을 사용하여 리스트의 각 요소를 문자열로 변환하고 공백으로 연결하는 방식으로 출력 형식을 수정하였다.

import sys

numbers = list(map(int, sys.stdin.readline().strip().split()))

while numbers != [1, 2, 3, 4, 5]:
    for i in range(4):
        if numbers[i] > numbers[i + 1]:
            numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
            print(" ".join(map(str, numbers)))

 

➡️ 정답 코드

import sys

numbers = list(map(int, sys.stdin.readline().strip().split()))

while numbers != [1, 2, 3, 4, 5]:
    for i in range(4):
        if numbers[i] > numbers[i + 1]:
            numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
            print(" ".join(map(str, numbers)))