https://www.acmicpc.net/problem/1838
정렬이 완료되었을 때 변수 i에 저장되어 있는 값을 구하는 문제다
[틀린 코드: 도현이 코드 그대로 사용]
for (i=0; i<N; i++) {
flag = 0;
for (j=0; j<N-1; j++) {
if (A[j] > A[j+1]) {
flag = 1;
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
if (flag == 0) {
break;
}
}
태국이를 이기기 위해 도현이가 작성한 코드다.
버블 정렬로 앞에서부터 순차적으로 요소를 정리하다가
더 이상 정렬할 필요가 없을 때 i를 출력한다.
이 코드를 파이썬 코드로 작성해서 제출했다.
[결과]
시간 초과가 났다. 당연하다.
문제에서 주어진 요소의 개수는 500,000
개이고 위의 코드는 O(n^2)
이다.
그럼 연산의 양은 250,000,000,000
개로 주어진 2초내에 계산을 끝낼 수 없다.
[정답]
문제의 i가 의미하는 것을 생각해보면 쉽게 풀 수 있다.
i는 더 이상 정렬을 하지 않아도 되서 멈췄을 때, 몇번 정렬이 이루어졌는지를 의미한다.
버블 정렬은 정렬을 한번씩 할 때마다 가장 큰 값이 가장 뒤로 이동한다.
따라서 [뒤로 이동한 값] 중 [가장 많이 이동한 거리]를 찾으면 된다.
즉, [정렬 전 인덱스 - 정렬 후 인덱스 > 0] 인 값 중 가장 큰 값 을 찾으면 된다.
import sys
from collections import defaultdict
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().rsplit()))
before = defaultdict(int)
for i,num in enumerate(a):
before[num]=i
a.sort()
after = defaultdict(int)
for i,num in enumerate(a):
after[num] = i
answer = 0
for num in before:
minus = before[num] - after[num]
if (minus > 0 and minus > answer):
answer = minus
print(answer)