[Python 3] BOJ - 1377 "버블 소트"

 # 문제 링크 : https://www.acmicpc.net/problem/1377

1377번: 버블 소트

  # 풀이 :

개인적으로 이 문제의 핵심은 규칙성 이해라고 생각한다.

<그림 1. i = 1>

 위 그림 1은 버블 소팅의 바깥 반복문, 즉 i가 1인 경우이다. 첫번째 사이클이 끝나면 배열의 최대값 10은 교환을 통해 맨 마지막 인덱스에 들어간다. 마지막 인덱스에 들어갈 수 밖에 없으므로 10은 인덱스가 계속 증가한다. 반대로, 10과 교환되는 수들(2, 5, 3)은 인덱스가 감소한다. 따라서, 임의로 인덱스가 증가하는 방향으로 바뀌는 이동은 빨간색 화살표로 나타냈다. 반대로 인덱스가 감소하는 방향으로 바뀌는 이동은 파란색 화살표로 나타냈다.

 배열 di-j의 정의는 최종적으로 정렬되야하는 위치에 가기 위해 i번째 사이클 중 j번째 교환에서 어느 방향으로 몇 칸 움직였는지를 나타내는 배열이다. 그림1에서는 움직임의 방향을 색깔별로 구분하였지만, 배열 d에서는 빨간색 움직임은 음수로, 파란색 움직임은 양수로 나타냈다. 따라서, 배열 d1-2의 마지막 원소 -2의 뜻은 원래 정렬하면 마지막에 와야하는 수가 인덱스가 증가하는 방향으로 2칸 움직였다는 뜻이다.

<그림 2. i = 2>

 따라서, 그림 2의 마지막 배열은 d2-2가 최종적으로 정렬을 위해 각 원소가 어느 방향으로 몇칸 이동했는지를 나타내는 배열이 된다. 그런데 첫번째 사이클, 즉 i가 1일때는 최대값인 10이 마지막 인덱스에 들어갔다. 또한 두번째 사이클, 즉 i가 2일때는 두번째 최대값인 5가 뒤에서 두번째 인덱스에 들어갔다. 따라서, 가장 마지막에 정렬되는 수는 정렬 후 인덱스와 초기 인덱스가 다른 수 중 가장 작은 값이다.

 따라서 최종적인 배열 d에서 양수라면 그 수는 원래의 인덱스를 가기 위해 최종적으로 인덱스가 감소하는 방향으로 움직였다는 뜻이고, 반대로 음수라면 그 수는 원래의 인덱스를 가기 위해 최종적으로 인덱스가 증가하는 방향으로 움직였다는 뜻이다. 따라서, 최종적인 배열 d에서 음수는 마지막 사이클이 될 수 없기에 양수 중 가장 큰수가 가장 마지막 사이클에 끝난 수라고 할 수 있다.

 또한 추가적으로 음수방향(인덱스가 증가하는 방향)으로의 이동은 사이클에 상관없이 발생하지만, 양수방향(인덱스가 감소하는 방향)으로의 이동은 각 원소 당 최대 1번이기 때문에, 결국 사이클과 같은 의미를 가진다.

<그림 3. 정렬 종료 시>

 그림 3은 그림1과 2의 과정이 끝난 후의 결과이다. d[3]인 -3은 10이 첫번째 사이클에서 음수방향으로 3번 이동했음을 의미한다. d[2]인 -1은 5가 첫번째 사이클에서는 양수 방향으로 움직였지만, 두번째 사이클에서는 음수 방향으로 2번 이동했기에 결과적으로 음수방향으로 1번 이동했음을 의미한다. 그런데 d[2]와 d[1]은 모든 사이클에서 양수 방향으로 이동했다. 그런데, 각각 각 사이클 마다 한번씩 움직였고 총 사이클은 2번이었으므로 d[1] = d[2] = 2이다. 즉, 최종적인 배열에서 양수인 값은 그 원소가 목표 인덱스에 들어갈 때 까지 몇번의 사이클을 거쳤는지에 대한 정보를 담고 있다.

 따라서, d중 양수면서 절댓값이 가장 큰 값이 가장 마지막 사이클에 목표 인덱스에 들어갔다는 뜻이므로 이것이 정답이 된다.

 

 # 코드

import sys

# num : 총 원소의 수
# a : 본문의 배열 d
num = int(sys.stdin.readline())
a = []
ans = 0
for i in range(num):
    # a를 [(각 원소 값, 초기 인덱스)...] 꼴로 바꾼다
    temp = int(sys.stdin.readline())
    a.append((temp, i))
    
# 정렬
a.sort()
for i in range(num):
    # i = 각 원소의 목표 인덱스
    # 따라서, 초기인덱스 - 목표인덱스가 양수인 경우 최댓값 갱신
    if a[i][1] - i > ans:
        ans = a[i][1] - i
        
# 문제에서 끝나는 사이클이 아닌 끝난 후 다음 사이클을 구해야 하므로 +1을 정답으로 출력
print(ans + 1)