[백준 | Python] #31003 - 언젠가 정렬이 될 수 있으면 좋겠네.

31003번: 언젠가 정렬이 될 수 있으면 좋겠네.

문제

양의 정수로 $N$개로 이루어진 수열을 인접한 원소끼리 순서를 변경하여 사전 순으로 가장 앞에 오게 정렬하여라. 단, 인접한 원소가 서로소일 때만 순서를 변경할 수 있다.

 

아이디어

처음에는 버블 정렬과 유사한 방식을 떠올렸다.

첫째 원소부터 반복하며 현재 원소가 앞의 원소보다 작고 순서를 변경할 수 있다면 순서를 변경하고 이를 가능할 때까지 반복한다.

하지만 이런 방식은 문제가 있다.

[4 2 3]은 위의 방식으로 정렬하면 [3 4 2]가 아닌 [4 2 3]의 결과를 얻게 된다.

따라서 인접한 원소를 비교하며 그리디하게 변경하는 것은 문제가 있다.

 

이에 따라 떠올린 솔루션은 다음과 같다.

 

첫째 원소부터 반복한다.

현재 원소가 앞의 원소들에 대해 어디까지 순서가 변경 가능한지 확인한다.

위 과정에서 현재 원소보다 앞의 원소가 크다면 그 인덱스 중 가장 작은 인덱스를 기록해 둔다.

현재 원소를 위에서 기록한 인덱스로 보내고 기존에 위치하던 원소들은 뒤로 한칸씩 민다.

 

이렇게 하면 사전순의 의미를 실제로, 그리고 직관적으로도 살리며 정렬할 수 있다.

두 개의 for loop을 돌면서 gcd를 구하니 시간복잡도는 $O(N^2 \log M)$.

 

코드

from math import gcd

n = int(input())
nums = list(map(int, input().split()))

for i in range(n):
    target = None
    for j in range(i-1, -1, -1):
        # 변경 불가. 룹 종료
        if gcd(nums[i], nums[j]) != 1:
            break
        # 현재 원소보다 앞의 원소가 더 큼 -> target 변수에 기록
        if nums[j] > nums[i]:
            target = j
    
    # 변경할 윈소가 없다면 스킵
    if target == None:
        continue
    # 변경할 원소의 위치까지 순서를 차례로 변경
    for j in range(i, target, -1):
        nums[j], nums[j-1] = nums[j-1], nums[j]

print(*nums)

 

숏코딩

숏코딩도 해보았다. 171 bytes.

알고리즘을 수정하면 더 줄일 수 있을 것 같은데 쉽사리 떠오르지 않는다.

import math
n,*a=map(int,open(0).read().split())
for i in range(n):
 t=k=i
 while(math.gcd(x:=a[i],a[k-1])<2)*k:
  if a[k:=k-1]>x:t=k
 a=a[:t]+[x]+a[t:i]+a[i+1:]
print(*a)

 

 

후기

현재 골드 1로 평가되어 있는데 그 정도는 아닌 것 같다.골드3 정도가 무난할 듯