[백준] 나무 조각

문제보기 - https://www.acmicpc.net/problem/2947

문제명    - 나무 조각

난이도    - B1

문제유형 - 구현

풀이일자 - 25.03.08

 

📌 문제 탐색하기

• 1~5까지 중복되지 않은 조각을 입력받음
• 두 인접한 조각을 비교하여 큰 숫자가 오른쪽으로 이동하도록 교환 -> 버블정렬
• 조각이 이동할 때마다 상태를 출력

 

🛠 시간복잡도 확인

• 최악의 경우 [5, 4, 3, 2, 1]에서 총 10번(4+3+2+1)의 비교 및 교환 발생
• 버블 정렬과 동일한 O(N²) 연산 수행

 

📌 코드 설계하기

1. 다섯 개의 정수를 입력받고 리스트에 저장하기
   • list(map(int, sys.stdin.readline().split())) 활용
2. 리스트에서 인접한 두 요소를 비교하기
   
   • 정렬이 완료될 때까지 반복 while N != sorted(N)
   • 리스트에서 인접한 두 요소를 비교 N[i] > N[i+1]
   • if N[i] > N[i+1]: 앞의 값이 더 크면 두 값을 교환 -> temp활용
3. 교환 후 현재 리스트 상태 출력하기
   • 리스트를 숫자만 출력하기 위해 print(*N) 활용

 

📌 정답 코드(1회차)

import sys

# 1. 다섯 개의 정수를 입력받고 리스트에 저장하기
N = list(map(int, sys.stdin.readline().split()))

# 2. 리스트에서 인접한 두 요소를 비교하기
while N != sorted(N):
    for i in range(4):
        if N[i] > N[i+1]:
            temp = N[i]
            N[i] = N[i+1]
            N[i+1] = temp
            print(*N) # 3. 교환이 일어날 때마다 리스트 상태 출력하기

 

 

🫧 버블 정렬 (Bubble Sort) 이란?

인접한 두 개의 숫자를 비교하면서 큰 숫자를 오른쪽으로 이동시키는 정렬 알고리즘
거품이 물 위로 떠오르는 것처럼 큰 숫자가 반복적으로 오른쪽 끝으로 이동한다고 해서 "버블 정렬"이라고 함.

•