문제
예제
풀이
문제 분석
C++코드도 나오고 복잡해보이지만, 결국 스왑(이중 for문에서 안쪽 for문이 몇 번 실행됏는지)을 몇 번해야 정렬이 완료되는지를 구하면 되는 문제이다.
-> 버블 정렬을 사용하는 것이 아니라, 버블 정렬로 정렬 하려면 몇 번의 교환이 필요한지를 구하는 문제(버블 정렬의 원리를 확실히 이해해야 함)
초기 접근
단순히 주어진 C++코드를 python코드로 변경해서 제출했다.
결과는 당연히 시간초과..
C++코드 해석
changed 값을 false로 놓고 swap이 일어나면(순서가 변경되면) changed값이 True로 변경
changed 값이 false로 유지될 경우(swap이 일어나지 않았으면) i값 출력
-> 스왑이 몇 번 일어났는지를 구하는 코드
풀이과정
안쪽 for문이 몇 번 수행됐는지를 어떻게 구할지에 대해서 아이디어가 필요하다.
-> 안쪽 for문에서 특정 데이터가 왼쪽으로 이동할 수 있는 최대 거리는 1이다.
--> 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 된다.
완성 코드
import sys
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
lst.append((int(input()), i)) // 리스트에 값과 인덱스 번호 같이를 같이 저장
s_lst = sorted(lst) // 리스트 정렬(퀵 소트(nlogn))
max = 0
for i in range(n): // 원래 리스트의 인덱스 번호에서 정렬 후 인덱스 번호 차이 구해서 max에 넣음
if max < s_lst[i][1]-i:
max = s_lst[i][1]-i
print(max+1) // 문제의 c++코드를 보면 for문의 i가 1부터 실행되기 때문에 결과값에 1을 더해서 출력