[백준] 31003번. 언젠가 정렬이 될 수 있으면 좋겠네. (Python 파이썬)

문제

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

1024 MB

348

115

104

46.222%

문제

N개의 양의 정수로 이루어진 수열 A=[A1,⋯,An]가 주어진다. 당신은 원하는 만큼 다음 조작을 할 수 있다. 조작을 하지 않는 것도 가능하다.

• 수열에서 인접한 원소가 서로소일 때, 그 두 원소의 순서를 바꾼다.

두 수의 최대공약수가 1인 경우 두 수를 서로소라고 한다. 이때, 조작 이후 사전 순으로 최소인 수열 A를 구해보자.

입력

첫째 줄에 수열의 길이 N이 주어진다. (1≤N≤3000)

둘째 줄에 N개의 양의 정수 A1,A2,⋯,An이 공백으로 구분되어 주어진다. (1≤Ai≤10^9)

출력

조작 이후 사전 순으로 최소인 수열 A를 한 줄에 공백으로 구분하여 출력한다.

예제 입력 1 복사

5
7 3 4 2 6

예제 출력 1 복사

3 4 2 6 7

노트

어떤 수열이 다른 수열보다 사전 순으로 작다는 것은 다음을 의미한다.

• 두 수열 중 첫 번째 수가 작은 쪽이 사전 순으로 작다.
• 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 작은 쪽이 사전 순으로 작다.
• 길이가 0인 수열은 다른 어떤 수열보다 사전 순으로 작다.

사전 순으로 최소인 수열은 다른 모든 수열보다 사전 순으로 작거나 같은 수열을 말한다.

풀이

2023년 12월 월간 향유회 E 번으로 나온 위상정렬 문제.

꽤 쉽게 풀렸음에도 다 풀고나서 골드1 문제라서 깜짝 놀랐다.. 이딴게 골드1 ?? 

 

푼지 좀 되었는데 까먹을까봐 다시 회고해봅니다. 

 

풀이

 

서로소 인 두 수에 대해서는 자리를 바꿀 수 있고, 순서를 바꿀 수 없다. 

순서를 바꿔서 사전 순으로 최소인 (작은 숫자부터 오름차순) 수열 A 를 출력하면 된다. 

 

예를 들어, 예제의 입력 [7,3,4,2,6] 에서 뒤의 4,2,6 은 서로 서로소 (2가 최대 공약수이므로) 가 아니므로 426 은 서로 자리를 바꿀 수 없다. 

이건 순서를 정하는 등수문제처럼 위상정렬 문제임을 알 수 있다. 

 

수열에서 두 숫자를 고른 모든 경우에서 서로소가 아닌 경우에 방향을 지정하여 edge 를 저장하면 되는데, 

파이썬에는 최소공약수를 구하는 라이브러리 (math.gcd) 가 있으므로, gcd != 1 이면 서로소가 아니라는 것을 이용한다.

 

위상정렬에서 제일 먼저 빼야될 숫자를 꼭 진입차수가 낮도록 설정하자. 

 

그러면 6이 제일 마지막에 있으므로, 

• 4 -> 2
• 4 -> 6
• 2 -> 6 

와 같이 방향그래프를 설정할 수 있다.

 

여기서 주의할 점은 A 가 최대 10^9 이다. 

그래서 방향그래프와 진입차수를 실제 숫자가 아닌 인덱스로 설정한다. 

 

 

그리고 진입차수에서 숫자를 뺄 때, 작은 숫자부터 뺄 수 있도록 우선순위 큐에 넣는다. 

 

import heapq
import math

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

answer = []
graph = [[] for i in range(n)]
indegree = [0] * (n)

for i in range(n):
    for j in range(i+1,n):
        if math.gcd(nums[i],nums[j]) != 1:
            graph[i].append(j)
            indegree[j] += 1

def topology_sort():
    h = []

    for i in range(0, n): # 진입차수가 0인 노드를 큐에 삽입
        if indegree[i] == 0:
            heapq.heappush(h,(nums[i],i))

    for i in range(n):
        now = heapq.heappop(h)
        answer.append(now[0])

        for i in graph[now[1]]:
            indegree[i] -= 1
            if indegree[i] == 0:
                heapq.heappush(h, (nums[i], i))
    else:
        print(' '.join(map(str, answer)))

topology_sort()

 

p.s. 나도 플래가고싶다. 플래 언제가지..