[백준 1838] 버블 정렬 (python)

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

1838번: 버블 정렬

버블 정렬 문제

버블 정렬을 이용해서 정렬 할 때, 정렬이 완성된 경우 탐색 중단 하고, 그 때의 정렬의 i 값을 찾는 문제

아이디어를 떠올리는데 힘들었고 정렬에 대해 찾아보고 생각해냈으나, 버블정렬에 대해 조금 생각해보면 풀 수 있는 문제

내가 푼 정답코드

import sys	
N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

not_sort_arr = {} # 정렬하기 전 각 숫자들의 현재 인덱스를 저장
for i in range(N):
    not_sort_arr[arr[i]] = i

arr.sort()
sort_arr = {} #정렬 후 각 숫자들의 현재 인덱스를 저장
for j in range(N):
    sort_arr[arr[j]] = j

result = 0
for k in arr:
    result = max(result, not_sort_arr[k] - sort_arr[k]) # 정렬 전과 후의 인덱스 차이 중 가장 큰 애가 찾는 값

print(result)

문제에 주어진 정렬 그대로 코드로 가져와서 쓰면 당연한 이야기지만 시간초과가 뜬다 (버블 정렬은 시간복잡도가 무려 O(n^2)이므로)

가장 먼저 든 생각은 원래 버블 정렬처럼 2중 for문으로 구성할 경우 100% 시간초과가 날걸 생각하고 단일 for문을 이용해서 해결할 방법을 생각하기로 했다.

먼저 버블정렬의 개념에 대해서 생각해보면 크기에 따라 '1칸씩' 이동하는 특성을 가진다.

예를 들어 [6, 7, 21, 2, 13] 이란 숫자를 정렬한다고 생각해보자.

최종적으로 오름차순 정렬시 [2, 6, 7, 13, 21]의 순서로 정렬이 될 것이다. 여기서 버블 정렬을 이용할 경우 한칸씩 바꿔주는 과정을 거친다.

2는 4번째 자리에서 1번째 자리로 이동하기 위해 -3번을 이동

6은 1번째 자리에서 2번째 자리로 이동하기 위해 +1번을 이동

7은 2번째 자리에서 3번쨰 자리로 이동하기 위해 +1번을 이동

...

이런 과정을 거쳐서 이동하게 된다

문제에서 요구하는 정렬 과정이 완료되었을 때, 변수에 저장되어 있는 i 값을 구하란 말은 즉 오른쪽으로 제일 많이 이동한 녀석의 이동 횟수를 구하란 말과 동일하다. 최종적으로 정렬이 완료 되기 위해선 제일 많이 이동한 녀석만큼 정렬 이동해야 정렬이 완성됐다고 할 수 있기 때문이다. (이해가 안된다면 직접 노트에 적어서 정렬에 대해 생각해보자)

이를 위해 정렬 전의 값과 인덱스를 딕셔너리 형태로 받아주고, 마찬가지로 정렬 후의 값과 인덱스를 딕셔너리 형태로 넣어주었고, 두 딕셔너리에 대해 저장된 key값에 대한 value(인덱스) 차이 중 가장 큰 친구를 구해 출력해주었다.

---

느낀 점

정렬에 대해 다시 고민해볼 수 있는 문제였다. 실제 문제 난이도에 비해 등급이 높게 설정되어있지 않나? 싶은 생각이 드는 문제였다.

무엇보다 버블 정렬의 특성인 1칸씩 이동한다를 깨닫고 문제 주어진 요구사항만 생각하면 쉽게 접근할 수 있는 문제였다. 쉽사리 생각긴 어려우면서도 어렵지 않은 딱 중간 수준의 문제였던거 같다.

다 좋은데 시간초과 늪과 앞에 주어진 예시에 현혹되지만 않으면 잘 해결 할 수 있던 문제!