백준 [자바 java] 2252 : 줄 세우기

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

2252번: 줄 세우기

4개월 전에 풀려고 시도했다가 못 푼 문제를 다시 풀어봤다.

 

학생의 수와 키를 비교한 횟수가 주어진다. a와 b가 주어지면, a가 무조건 b앞에 있어야 한다는 의미이다.

 

나는 list를 두 개를 놓고, 하나는 학생마다 뒤에 와야 하는 학생을 저장하고, 하나는 앞에 오는 학생을 저장하는 리스트를 만들었다. 

a와 b를 입력받으면, list[b]에 a를 넣고, list2[a]에 b를 넣었다. 

그리고 list[k]가 비어있으면 k가 맨 앞에 올 수 있다는 의미이므로 이를 큐에 넣었다. 그리고 bfs와 유사한 방식으로 큐에 있는 수를 하나씩 빼서 이 수가 앞에 있어야 하는 사람의 list에서 remove 했다.(이미 줄을 섰으므로)

 

처음에는 큐에 넣는 방법을 쓰지 않고, 그냥 빈 리스트를 계속해서 탐색하는 알고리즘을 짜서 시간초과가 나왔다.(시간복잡도 O(N^3))

 

 int[] vis = new int[n+1];

        while(true){
            for(int i = 1;i<=n;i++){ // 빈 리스트 탐색
                if(vis[i] == 0){
                    if(list[i].size() == 0){ // 빈 리스트 발견
                        ans.add(i);
                        vis[i] = 1;
                        for(int j = 0;j<list2[i].size();j++){
                            if(list[list2[i].get(j)].size() != 0){
                                list[list2[i].get(j)].remove(0);
                            }
                        }
                    }
                }
            }
            if(ans.size() == n) break;
        }

이후 위상정렬의 개념을 익히고 다시 풀어보니 맞았습니다가 나왔다. 앞으로 시간복잡도 줄일 때 스택, 큐를 사용하는 것을 고려해봐야겠고, 위상정렬 개념을 잘 기억하고 있어야겠다.

 

import java.util.*;
import java.io.*;
import java.math.*;


public class Main {



    public static void main(String[] args) throws IOException {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<Integer>[] list = new LinkedList[n+1];
        List<Integer>[] list2 = new LinkedList[n+1];

        for(int i = 0;i<=n;i++){
            list[i] = new LinkedList<Integer>();
            list2[i] = new LinkedList<Integer>();
        }

        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list[b].add(a);
            list2[a].add(b);
        }

        LinkedList<Integer> ans = new LinkedList<>();

        int[] vis = new int[n+1];

        Queue<Integer> q = new LinkedList<>();

        for(int i = 1;i<=n;i++){// 처음부터 비어있는 리스트 탐색해서 큐에 넣기
            if(list[i].size() == 0){
                q.add(i);
            }
        }

        while(!q.isEmpty()){
            int now = q.poll();
            sb.append(now + " ");

            for(int j = 0;j<list2[now].size();j++){
                int kk = list2[now].get(j);
                if(list[kk].size() != 0){
                    list[kk].remove(0);
                }
                if(list[kk].size() == 0) q.offer(kk);
            }

        }


        System.out.println(sb);



    }
}