[백준 2947번] 나무 조각 - python

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

📌 문제 탐색하기

목표

• 나무 조각 5개를 앞에서 부터 하나씩 바꿔가며 정렬하기
• 두 개의 나무 조각에 써져있는 수를 비교하며 앞 조각의 수가 뒷 조각의 수보다 크면 위치를 바꾼다.

입력값

• 1, 2, 3, 4, 5 숫자가 랜덤으로 배치되어 한 줄에 입력된다.
  • ex) 2 1 5 3 4

출력값

• 두 조각의 순서가 바뀔 때마다 조각의 순서를 출력한다.
  • ex)
  • 1 2 5 3 4 1 2 3 5 4 1 2 3 4 5

📌 코드 설계하기

해결 아이디어

• 차근차근 수를 비교하며 정렬을 한다.
• 완료된 정렬 결과와 실제 정렬 결과와 비교를 한 후 일치하지 않으면 다시 처음부터 비교하며 정렬을 진행한다.

📌 정답 코드

block = list(map(int, input().split()))

while (block != sorted(block)):
    for i in range (len(block) - 1):
        if(block[i] > block[i+1]):
            temp = block[i]
            block[i] = block[i+1]
            block[i+1] = temp
            print(*block)

시간 복잡도 계산해보기

• 입력 처리
  • list(map(int, input().split())) → O(N)
• while문
  • sorted(block) → ****O(N log N)
  • block != sorted(block) 리스트 비교 → O(N)
  • 합치면 → O(N log N)
  • for 문
    • 원소 비교 및 스왑 → O(N)
    • print(*block) → O(N)
    • for문을 다 돌아서 합치면 → O($N^2$)
• while문 루프 전체
  • 조건 검사 + for 루프 → O($N^2$)
  • while문을 다 돌아서 합치면 O($N^3$)

최종 시간 복잡도: O($N^3$)

다른 풀이

• python에서 스왑은 간단하게 해결이 가능하다.
• 계속 sort를 하며 while문 내에서 비교를 해서 시간 복잡도를 높이지 말고 다른 방법을 써보았다. unsorted라는 flag를 둬서 if문을 만족하지 못해면 False로 계속 둬서 while문이 더 이상 돌아가지 못하게 한다.

block = list(map(int, input().split()))
unsorted = True
while (unsorted):
    unsorted = False
    for i in range (len(block) - 1):
        if(block[i] > block[i+1]):
            block[i], block[i+1] = block[i+1], block[i]
            unsorted = True
            print(*block)