💡 문제
버블 소트 알고리즘을 다음과 같이 C++로 작성했다.
위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.
입력
첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.
출력
정답을 출력한다.
💭 접근
이 문제는 위 코드를 이해하고, 입력 n의 최대가 500,000인 경우 시간 초과 없이 위 코드와 같은 결과를 출력하도록 만들어야 한다. 당연히 버블 소트를 사용하면 시간 초과가 발생하게 된다.
먼저 예제로 위 코드를 이해해보자.
예제 1 [10, 1, 5, 2, 3]
1회 순회 -> [1, 5, 2, 3, 10]
2회 순회 -> [1, 2, 3, 5, 10]
3회 순회 -> 정렬할 원소 없음 (정답 : 3)
그렇다면 어떻게 버블 소트를 사용하지 않고 위 코드와 같은 동작을 하도록 구현할 수 있을까?
아래 그림을 보며 이해해보자.
우선 정렬이 1회 실행되었을 때 그림이다.
이때 가장 큰 수인 10이 맨 뒤로 가고, 나머지 숫자들은 각각 순서를 유지하고 그대로 한칸 씩 앞으로 이동한 것을 볼 수 있다.
정렬이 2회 수행되었을 때 그림이다.
10 다음으로 큰 5가 뒤로 이동하고, 또 다시 5보다 뒤에 있던 수들은 순서를 유지한채 한칸 씩 앞으로 이동한 것을 볼 수 있다.
여기서 해결방법을 도출해 낼 수 있는데, 각각의 수들이 이동한 칸 수를 보자.
[10, 1, 5, 2, 3] -> [1, 2, 3, 5, 10]
1: 앞으로 한칸 이동
2: 앞으로 두칸 이동
3: 앞으로 두칸 이동
5: 뒤로 두칸 이동
10: 뒤로 네칸 이동
이를 미루어 보아 리스트를 순회하며 정렬을 1회 실행할 때마다 각 수들의 자리가 바뀌는 것을 볼 수 있고, 가장 이동을 많이 숫자를 통해 순회가 몇번 이루어졌는지 알 수 있다.
따라서 처음 수를 입력받을 때,
for i in range(n):
a.append((int(input()), i))
sorted_a = sorted(a)이처럼 처음 상태의 인덱스를 함께 저장하고, 정렬을 먼저 수행한 뒤,
아래와 같이 인덱스의 차이가 가장 큰 수를 찾으면 된다.
for i in range(n):
ans = max(ans, sorted_a[i][1] - i)
print(ans + 1)이때 주의할 점으론 인덱스의 차이가 가장 큰 값은 순회가 이루어진 횟수이고, 문제에서 주어진 코드는 마지막으로 순회하여 정렬이 완료되었을 때 순회가 종료되므로 마지막 정답에 +1을 해주어야 한다.
📒 코드
import sys
input = sys.stdin.readline
n = int(input())
a = []
for i in range(n):
a.append((int(input()), i))
sorted_a = sorted(a)
ans = 0
for i in range(n):
ans = max(ans, sorted_a[i][1] - i)
print(ans + 1)💭 후기
버블 소트의 원리를 잘 이해하고 있었다면 어렵지 않게 해결했을 것 같은 문제였다. 계속 복습하자.
🔗 문제 출처
https://www.acmicpc.net/problem/1377
