[백준 1377번] 버블 소트 (Python/파이썬)

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

1377번: 버블 소트

문제를 보고 그냥 바로 C++코드를 그대로 갖다쓰면 안되나? 했지만 당연하게도 숫자범위가 50만...

시간복잡도가 N * N인 버블 정렬을 사용하면 시간초과가 날게 뻔했다.

구현이 어려운 문제는 아니고 아이디어때문에 골드2인거 같다.
C++ 코드를 해석하면 정렬이 완전히 되었을때 한줄 반복을 몇번수행했냐 라는 코드다.
따라서 정렬이 완성되고 나서의 i값에 +1을 하면 된다.

 

아이디어는 버블정렬의 특징상 한번 정렬을 수행할때 마다 리스트의 왼쪽으로는 최대 한번밖에 이동하지 못하므로 

정렬 전과 정렬 후의 인덱스 위치를 비교하여 왼쪽으로 얼마나 이동했는지 구하면 끝 

따라서 (정렬 전의 인덱스 - 정렬 후의 인덱스)의 최댓값 + 1을 하면 된다.

나는 딕셔너리로 풀었는데 다른 사람들은 인덱스를 숫자와 함께 튜플로 저장했던데 상당히 좋은 방법인거 같다.

코드는 다음과 같다.

import sys
input = sys.stdin.readline

def Sol():
  N = int(input())
  dic = {}
  for i in range(N):
    dic[i] = int(input())
  sort_num = sorted(dic.values())

  sort_dic = {}
  for i in range(len(sort_num)):
    sort_dic[i] = sort_num[i]

  ## 정렬 후 딕셔너리 뒤집기
  sort_dic = dict(map(reversed, sort_dic.items())) 
  max = 0
  j = 0
  for i in dic.values():
    if max < j - sort_dic[i]:
      max = j - sort_dic[i]
    j += 1
  print(max + 1)
     

if __name__ == "__main__":
  Sol()

 

 

아이디어만 생각해낸다면 구현은 그리 어렵지 않다.

 

코드, 글에 대한 질문과 조언 모두 환영합니다.