이런건 어떻게 푸는거야 (#1377 버블소트)

#1377 버블 소트 https://www.acmicpc.net/problem/1377

 

단순 코드를 구현하라는 문제인줄 알고 그냥 풀어봤다.

 

# bool changed = false;
# for (int i=1; i<=N+1; i++) {
#     changed = false;
#     for (int j=1; j<=N-i; j++) {
#         if (A[j] > A[j+1]) {
#             changed = true;
#             swap(A[j], A[j+1]);
#         }
#     }
#     if (changed == false) {
#         cout << i << '\n';
#         break;
#     }
# }

from sys import stdin

input = stdin.readline

changed = False
N = int(input())
A = [0] + [int(input()) for _ in range(N)]
for i in range(1, N + 1 + 1):
    changed = False
    for j in range(1, N - i + 1):
        if A[j] > A[j + 1]:
            changed = True
            # swap
            tmp = A[j]
            A[j] = A[j + 1]
            A[j + 1] = tmp

    if not changed:
        print(i)
        break

 

 

근데 계속 시간초과가 나더라.

 

그도 그럴 것이 버블 정렬은 시간복잡도가 O(n^2)이다.

 

 

문제가 요구하는 바를 다시 해석하면,

i 값을 출력하는 것인데,

 

버블 정렬 시, 몇 회차까지 정렬이 필요한지를 물어보는 것이다.

 

따라서, 이는 다음과 같이 구할 수 있다.

 

1. 정렬 전의 index를 저장하고

2. 가장 빠른 방법으로 정렬을 진행한다.

3. 정렬 후의 index에서 정렬 전의 index를 뺀 값 중 가장 큰 값에 1을 더하면 문제가 원하는 답이 된다.

 

 

나는 다음 블로그를 참고했다.

 

https://infinitt.tistory.com/229

백준(boj) 파이썬 - 1377 번 : 버블 소트

 

 

 

따라서 다음과 같이 구현할 수 있다.

n = int(input())
a = [[int(input()), i] for i in range(n)]
sorted_a = sorted(a)

# print(a)
# print(sorted_a)

result = []
for i in range(n):
    result.append(sorted_a[i][1] - a[i][1])

print(max(result) + 1)

 

 

원리를 알고나면 굉장히 심플하게 해결되는 문제이다.

 

조금 신기했다.