[BOJ] 1377 버블 소트 Python

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

문제 해석

해당 문제는 버블소트 코드를 읽고 어떠한 출력 값이 나와야하는지 파악한 후, 다른 코드로 해당 출력 값이 나오도록 하는 것이 목적이다.

위에 코드의 결과는 버블소트 몇번째 턴에 정렬이 다 되는지 확인하는 문제이다.

[10,1,5,2,3] 를 버블 소트를 정렬한다면,

10,1,5,2,3 1번
1,5,2,3,10 2번
1,2,3,5,10 3번

3번 만에 정렬이 끝나게 된다. (사실 2번 턴이긴한데, 해당 코드에서 i 값이 1부터 시작한다. 그래서 이미 정렬되어 주어진다고 하더라도 1이 출력된다.)

문제 해결

위에 주어진 대로 코드를 치게 되면, 시간초과가 난다.
즉 다른 방법을 찾아서 몇 번째에 버블소트가 끝나는지 알아야 한다.

다음은 답 코드이다. 코드를 보며 설명한다.

# 전체코드
import sys

N = int(sys.stdin.readline().strip())
A = []

for i in range(N) :
    A.append([i, int(sys.stdin.readline().strip())])

check = sorted(A,key=lambda x:x[1])

m = 0

for i in range(N) :
    temp = check[i][0] - i 
    m = max(m, temp)
        
print(m+1)

# 입력 값 받기 
N = int(sys.stdin.readline().strip())
A = []

# 여기서 입력을 받을 때, 몇 번째로 받는지 인덱스 값도 같이 저장한다.
# 먄약 10,1,5,2,3 을 받는다면, [[0,10],[1,1],[2,5],[3,2],[4,3]] 로 A에 저장된다.
for i in range(N) :
    A.append([i, int(sys.stdin.readline().strip())])

# 이제 입력받은 값 기준으로 sorted를 한다. 여기서 sorted를 한 이유는, 퀵소트가 가장 빠른 정렬이기 때문에 써줬다.
check = sorted(A,key=lambda x:x[1])

# 몇 번째에 정렬이 완성되는지 찾기 위해서 m 값을 초기화
m = 0

여기가 하이라이트임!

for i in range(N) :
    temp = check[i][0] - i 
    m = max(m, temp)
        
print(m+1)

다음과 같이 10,1,5,2,3 수가 주어지고 버블 정렬이 이루어진다면 계속 한칸씩 앞으로 밀리는 수들을 볼 수 있다.
그렇다면 모든 수를 돌면서
처음에 있던 인덱스 자리의 위치와, sorte된 인덱스 위치를 빼서 가장 큰 값을 출력하면, 몇 번만에 정렬이 완료되었는지 확인 할 수 있다.

그래서 다음과 같이 뺄셈을 하게 되면, 최고값은 2가 나온다. 그리고 문제에서 주어진 버블소트 코드는 i가 1부터이고, 내가 작성한 코드는 0부터 이기 때문에, 출력은 최고값 +1 을 해준다.