Baekjoon[2252] - 줄 세우기

링크

2252번: 줄 세우기

문제설명

• 주어진 조건대로 정렬

문제풀이

• 위상정렬

문제코드

package baekjoon;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main2252 {

    public static int N;
    public static int M;
    public static ArrayList<Integer>[] adj;
    public static int[] cnt;

    public static LinkedList<Integer> q;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/baekjoon/2252.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cnt = new int[N];

        adj = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adj[i] = new ArrayList<Integer>();
        }

        int from, to;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken())-1;
            to = Integer.parseInt(st.nextToken())-1;
            adj[from].add(to);
//            선수과목
            cnt[to]++;
        }

//        위상정렬
        q = new LinkedList<Integer>();

//        adj cnt 0인 애들 q에 집어넣기
        for (int i = 0; i < N; i++) {
            if(cnt[i]==0) {
                q.add(i);
            }
        }

        int now;
        int ls;
        int c;
        while(!q.isEmpty()) {
            now = q.poll();
            sb.append(now+1).append(" ");
            ls = adj[now].size();
            for (int i = 0; i < ls; i++) {
                c=--cnt[adj[now].get(i)];
                if(c==0) {
                    q.add(adj[now].get(i));
                }
            }
        }
        System.out.print(sb);
    }
}

아쉬운점

• 상황에 맞는 최적화된 자료구조를 잘 사용하지 못하였음
  • 인접리스트를 구현할 때는 데이터의 삭제,추가가 상대적으로 적음
    • ArrayList써야함
    • LinkedList쓰면 시간초과 남

잘한점

• 위상정렬을 구현하였다.

  • 추후 포스팅

• O(N)

  • N<32000이라 인접행렬을 구하면 32000^2라 메모리 초과임

• 최적화

  • Stringbuilder사용

  • List.get(i)[idx]접근하는데에 시간이 오래 걸림

  • for (int i = 0; i < ls; i++) {
           cnt[adj[now].get(i)]--;
           if(cnt[adj[now].get(i)]==0) {
               q.add(adj[now].get(i));
           }
       }

    를 바꿈

  • for (int i = 0; i < ls; i++) {
           c=--cnt[adj[now].get(i)];
           if(c==0) {
               q.add(adj[now].get(i));
           }
       }