[BOJ] 1377 - 버블 소트 (Python)

 

 

아이디어

 

버블 소트는 1회전마다 바로 뒤의 수보다 큰 앞의 수가 한 칸씩 뒤로 이동하며 정렬된다.

따라서 정렬 후 수들이 뒤로 이동한 거리의 최댓값을 구한다.

 

 

풀이

 

딕셔너리 A에 순서를 키로, 수를 값으로 저장하고, 수가 작은 순으로 그 순서를 정렬한다.

for문에서 정렬 전의 순서에서 정렬 후의 순서를 뺀 값의 최댓값을 res에 저장한 후, 1 증가시킨 res를 출력한다.

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    A = dict()
    for i in range(N):
        A[i] = int(input())
    A = sorted(A, key=lambda i: A[i])
    res = 0
    for i in range(N):
        res = max(res, A[i]-i)
    print(res+1)

solution()

 

 

세트는 순서가 보장되지 않아 람다식으로 수 기준으로만 정렬하면 제대로 정렬되지 않았다.

리스트의 경우 순서가 보장되어 수 기준으로만 정렬해도 정렬이 되나, 뒤집으면 마찬가지로 제대로 정렬되지 않았다.

# 1. 틀린 코드
A = set()
for i in range(N):
    A.add((int(input()), i))
A = sorted(A, key=lambda x: x[0])

# 2. 맞는 코드
A = set()
for i in range(N):
    A.add((int(input()), i))
A = sorted(A)

# 2. 맞는 코드
A = [(int(input()), i) for i in range(N)]
A.sort(key=lambda x: x[0])

# 3. 틀린 코드
A = [(int(input()), i) for i in range(N)][::-1]
A.sort(key=lambda x: x[0])

 

순서 정렬 시 딕셔너리를 사용하는 코드가 가장 효율적이었고, 세트를 사용하는 코드가 가장 비효율적이었다.

# 1.
A = set()
for i in range(N):
    A.add((int(input()), i))
A = sorted(A)

# 2. 1번 코드보다 메모리를 더 적게 사용하고 더 빠른 코드
A = []
for i in range(N):
    A.append((int(input()), i))
A.sort()

# 3. 2번 코드보다 더 빠른 코드
A = [(int(input()), i) for i in range(N)]
A.sort()

# 4. 3번 코드보다 메모리를 더 적게 사용하고 더 빠른 코드
A = dict()
for i in range(N):
    A[i] = int(input())
A = sorted(A, key=lambda i: A[i])