[백준/파이썬] 1377번 버블 소트 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1377번 버블 소트
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

버블 소트가 정렬을 완료하기까지의 패스 횟수를 구하는 문제입니다.

코드

import sys

n = int(sys.stdin.readline())
nums = [(0, -1)] + [(i, int(sys.stdin.readline())) for i in range(1, n+1)]

madmax = 0
nums.sort(key=lambda num: num[1])
for i in range(1, n+1):
    madmax = max(madmax, nums[i][0]-i)
print(madmax+1)

설명

각 원소의 원래 위치를 함께 저장해 값 기준 정렬한 뒤, 원래 인덱스 - 정렬 후 인덱스의 최댓값을 구합니다.

버블 소트 특성상 답은 그 최댓값에 1을 더한 값입니다.

---

• 백준 문제풀이 전체 목록 보기

---