[python/백준] 2947. 나무 조각(B1)

📌 문제 탐색하기

👉 문제바로가기

나무 조각에 쓰여있는 숫자 5개에 대해 인접한 숫자와 대소를 비교하고 위치를 바꾸어 오름차순으로 정렬하는 문제입니다. 오름차순으로 정렬하는 과정에서 중간 결과들을 출력해주면 됩니다.

알고리즘 선택

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘인 버블 정렬(단순 교환 정렬)을 사용하였습니다.

가능한 시간복잡도

배열의 크기가 N인 경우, N-1개의 아이템과 비교해야 합니다. 최악의 경우에는 모든 원소들을 교환해야 하므로 버블 정렬의 시간복잡도는 O(N^2)입니다. 이 문제에서는 원소가 5개만 있으므로 최악의 경우 연산 횟수는 약25회입니다.

📌 코드 설계하기

1. 처음 조각의 순서에 대한 input을 받아 리스트에 저장합니다.
2. 앞에서부터 두 값을 비교하여 더 큰 수가 앞에있는 경우 교환합니다.
3. 2번 과정을 배열이 끝날 때까지 반복하면서 원소의 순서가 바뀔때마다 그 결과를 출력합니다.
   👉 여기서 한 번의 사이클을 돌게되면 가장 큰 원소부터 가장 오른쪽에 정렬이 완료됩니다. 이후 정렬이 완료된 원소는 정렬할 대상 원소에서 제외하므로 비교해야하는 원소의 갯수는 1개씩 줄어들게 됩니다.

📌 정답 코드

import sys

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

for i in range(len(number) - 1):
  for j in range(0, len(number) - (i + 1)):
    if (number[j] > number[j + 1]):
      number[j], number[j + 1] = number[j + 1], number[j]
      print(*number)