문제
동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다.
동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다.
첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.
처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.
출력
두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.
예제 입력 1
2 1 5 3 4
예제 출력 1
1 2 5 3 4
1 2 3 5 4
1 2 3 4 5
예제 입력 2
2 3 4 5 1
예제 출력 2
2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5
문제 탐색하기
나무 조각들의 초기 배열을 정렬하는 과정에서 조건에 맞아 교환일 될 경우 출력하는 문제
주어진 조건:
나무 조각 5개 중 1부터 5까지 숫자 하나가 쓰여져 있음. 중복되는 숫자 없음.
초기에는 정렬되지 않은 상태.
위치를 바꿀 때 마다 조각의 순서를 출력하기 <- 이게 핵심
가능한 시간복잡도
while문과 for문을 사용하므로 O(n^2)의 시간 복잡도를 가짐.
알고리즘 선택
이 문제에서는 버블 정렬 (Bubble Sort) 알고리즘이 사용되었습니다. 버블 정렬은 인접한 두 요소를 비교하여 큰 값이 뒤로 가도록 반복하여 정렬하는 알고리즘입니다.
코드 설계하기
- 나무 조각들의 초기 배열을 입력받아 리스트로 저장합니다.
- 리스트의 각 인덱스를 순서대로 비교하면서 앞의 숫자가 더 크면 자리 교환을 수행합니다.
- 교환이 발생할 때마다 현재 배열 상태를 출력합니다.
- 정렬이 완료되었는지 확인하여 [1, 2, 3, 4, 5] 상태가 되면 반복을 종료합니다.
시도 회차 수정 사항
1회차
list_[i] = list_[i+1]
list_[i+1] = list_[i]처음에는 이렇게 작성을 했는데 예상한 값이 안 나와서 찾아본 결과, 이렇게 되면 값을 교환하게 되는 게 아니였음,, 그냥 덮어쓰기가 되는거라 다시 작성,,,,,,, 생각해 보니 바보 같은 실수를 해버림 ㅠ
코드 구현
import sys
list_ = list(map(int, sys.stdin.readline().split()))
while list_ != [1, 2, 3, 4, 5]:
for i in range(len(list_)-1):
if list_[i] > list_[i+1]:
list_[i], list_[i+1] = list_[i+1], list_[i]
print(' '.join(map(str, list_)))
