백준 2252 줄세우기 파이썬 풀이

난이도 : 골드3

풀이일 : 05044

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드 : deque 두 개 사용, 최초풀이

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
people = [[] for _ in range(N+1)]
mini = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    people[a].append(b)
    mini[b] += 1

order = deque()
queue = deque()
for x in range(1, N+1):
    if not mini[x]:
        queue.append(x)
        order.append(x)

while queue:
    i = queue.popleft()
    for j in people[i]:
        mini[j] -= 1
        if not mini[j]:
            queue.append(j)
            order.append(j)

for x in order:
    print(x, end=' ')

코드 구성

• 내 앞에 서야 하는 사람 정보 리스트에 저장, mini 배열 해당 인덱스 += 1
• 내 앞에 서야 하는 사람이 없다면, queue, order 추가
• queue 요소 popleft 후 people 해당 인덱스 리스트 속 요소들 앞 사람 -1
• 앞에 서야 하는 사람이 없어졌다면, 해당 인덱스 queue, order 추가
• order : 처음부터 끝까지 queue 추가된 순서 출력 (출력 형식 주의)

실행 결과

• 메모리 : 37796KB
• 시간 : 224ms
• 코드 길이 : 579B

---

풀이 코드 : deque 한 개 사용, 3차 풀이

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
people = [[] for _ in range(N+1)]
mini = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    people[a].append(b)
    mini[b] += 1

order = deque()
for x in range(1, N+1):
    if not mini[x]:
        order.append(x)
        print(x, end=' ')

while order:
    i = order.popleft()
    for j in people[i]:
        mini[j] -= 1
        if not mini[j]:
            order.append(j)
            print(j, end=' ')

코드 변화

• deque 두 개 사용에서 한 개 사용으로 변경
• 순서가 정해지는 대로 해당 요소 출력

실행 결과

• 메모리 : 38452KB
• 시간 : 212ms
• 코드 길이 : 528B

---

풀이 코드 : 리스트, 포인터 사용, 2차 풀이

import sys

N, M = map(int, sys.stdin.readline().split())
people = [[] for _ in range(N+1)]
mini = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    people[a].append(b)
    mini[b] += 1

order = []
pointer = 0
for x in range(1, N+1):
    if not mini[x]:
        order.append(x)

while pointer < len(order):
    i = order[pointer]
    pointer += 1
    for j in people[i]:
        mini[j] -= 1
        if not mini[j]:
            order.append(j)

for x in order:
    print(x, end=' ')

코드 변화

• deque 미사용, 리스트로 요소 추가
• popleft 대신 pointer로 요소 지칭
• 반복문 조건은 pointer가 order 길이보다 길어지기 전까지로 제한
• 리스트의 전 요소 마지막에 출력

실행 결과

• 메모리 : 37920KB
• 시간 : 208ms
• 코드 길이 : 519B

---

느낀점

다른 방법이 생각나서 시도해보고, 결과를 확인 하는 과정이 재밌었다.

리스트, 포인터 사용 코드는 시간초과가 나오나 궁금했는데, 오히려 실행 시간이 제일 빨랐다.

미세한 차이라서 크게 의미는 없는 것 같긴 하지만