[파이썬, Java] 2252. 줄 세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1 

3 2

1 3

2 3

예제 출력 1 

1 2 3

예제 입력 2 

4 2

4 2

3 1

예제 출력 2 

4 2 3 1

 

 

✨ 나의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input=br.readLine().split(" ");
        int N=Integer.parseInt(input[0]);       // 사람 수
        int M=Integer.parseInt(input[1]);       // 키를 비교한 횟수
        ArrayList<ArrayList<Integer>> arr=new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=N; i++){
            arr.add(new ArrayList<Integer>());
        }
        int[] cnt=new int[N+1];
        Queue que=new LinkedList();

        for(int m=0; m<M; m++){
            String[] ab=br.readLine().split(" ");
            int a=Integer.parseInt(ab[0]);
            int b=Integer.parseInt(ab[1]);
            arr.get(a).add(b);
            cnt[b]++;
        }

        for(int i=1; i<=N; i++){
            if(cnt[i] == 0){
                que.add(i);
            }
        }

        while(!que.isEmpty()){
            int num=(int)que.poll();
            bw.write(num+" ");
            for(Integer b : arr.get(num)){
                cnt[b]--;
                if(cnt[b] == 0 ){
                    que.add(b);
                }
            }
        }
        bw.flush();
    }
}

위상정렬

BufferedWriter를 이용해서 출력할 내용을 넣고, flush로 한 번에 출력한다.

하나씩 출력하는 것보다 효율이 좋음

 

# 실패
from collections import defaultdict
import sys
input=sys.stdin.readline

N, M=map(int, input().split())       # N=총 인원, M=키를 비교한 회수
dic=defaultdict(list)

for k in range(1, N+1) :
    dic[k]=[]

# A < B
for m in range(M) :
    a, b=map(int, input().split())
    dic[a].append(b)

result=sorted(dic, key=lambda x : len(dic[x]))[::-1]
print(*result)

딕셔너리에 key보다 키가 더 큰 사람 value 리스트를 담았다.

value 길이가 짧은 순으로 정렬했다.

이런 문제를 처음 풀어봐서 그냥 내가 아는 한에서 아이디어를 내봤지만 fail😅

 

 

🍟 다른 사람 풀이

# https://sungmin-joo.tistory.com/83
import sys
from collections import deque
input=sys.stdin.readline

n, m=map(int, input().split())
arr=[]
inDegree=[0 for i in range(32001)]
graph=[[] for i in range(32001)]
queue=deque()

for i in range(m) :
    a, b=map(int, input().split())
    arr.append([a, b])

for a, b in arr :
    inDegree[b]+=1		# b보다 작은 사람 수
    graph[a].append(b)		# a < b

for i in range(1, n+1) :
    if inDegree[i] == 0 :	# i번보다 작은 사람이 0명
        queue.append(i)

while queue :
    student=queue.popleft()
    #indegree가 0인 정점을 제거하고, 해당 정점이 참조하고있던 점들의 indegree를 감소
    for j in graph[student] :
        inDegree[j]-=1
        if inDegree[j] == 0 :
            queue.append(j)
    print(student, end=' ')

위상정렬

inDegree의 인덱스는 사람 번호, 값은 이 번호보다 작은 사람 수

inDegree의 값이 0인 인덱스부터 queue에 넣는다.

queue에서 뺀 순서대로 answer 리스트에 담는다.

tmp와 연결된 번호 중 inDegree[i]가 0인 번호는 queue에 추가한다.

 

# https://hongcoding.tistory.com/95
import sys
from collections import deque

n, m=map(int, sys.stdin.readline().split())

graph=[[] for _ in range(n+1)]
inDegree=[0 for _ in range(n+1)]
queue=deque()
answer=[]

for i in range(m) :
    a, b=map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    inDegree[b]+=1

for i in range(1, n+1) :
    if inDegree[i] == 0 :
        queue.append(i)

while queue :
    tmp=queue.popleft()
    answer.append(tmp)
    for i in graph[tmp] :
        inDegree[i]-=1
        if inDegree[i] == 0 :
            queue.append(i)

print(*answer)

위상정렬