[BOJ] 2252 줄 세우기 - JAVA

1. 문제

2252번: 줄 세우기

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

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

---

2. 풀이

입력

count[i]는 i번째 학생보다 큰 학생의 수를 저장한다.

student[i]는 i번째 학생보다 작은 학생들을 저장한다.

키를 비교한 결과를 입력받으면서 student[a]에 b를 추가한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] count = new int[N+1];
ArrayList<Integer>[] students = new ArrayList[N+1];
for(int i=1;i<=N;i++) students[i] = new ArrayList<>();
int a, b;
for(int i=0;i<M;i++){
   st = new StringTokenizer(in.readLine());
   a = Integer.parseInt(st.nextToken());
   b = Integer.parseInt(st.nextToken());
   ++count[b];
   students[a].add(b);
}

 

탐색 및 출력

1.  나보다 큰 사람이 없는 학생들만 queue에 추가한다.

2.  queue를 하나씩 탐색하면서 sb에 뽑은 학생 번호를 더한다.

3.  students[now]에 있는 학생들을 하나씩 방문하면서 count[다음 학생] 값에서 1을 뺀다. 뺀 값이 0인 학생들을 queue에 추가한다.

4.  탐색이 끝난 후 sb를 출력한다.

Queue<Integer> queue = new ArrayDeque<>();
for(int i=1;i<=N;i++) {
   if(count[i]==0) queue.offer(i);
}

StringBuilder sb = new StringBuilder();
int now;
while(!queue.isEmpty()){
   now = queue.poll();
   sb.append(now).append(' ');

   for(int n:students[now]){
      if(--count[n]==0) queue.offer(n);
   }
}

System.out.println(sb);

 

전체 코드

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

public class BOJ_2252_줄세우기 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      int[] count = new int[N+1];
      ArrayList<Integer>[] students = new ArrayList[N+1];
      for(int i=1;i<=N;i++) students[i] = new ArrayList<>();
      int a, b;
      for(int i=0;i<M;i++){
         st = new StringTokenizer(in.readLine());
         a = Integer.parseInt(st.nextToken());
         b = Integer.parseInt(st.nextToken());
         ++count[b];
         students[a].add(b);
      }

      Queue<Integer> queue = new ArrayDeque<>();
      for(int i=1;i<=N;i++) {
         if(count[i]==0) queue.offer(i);
      }

      StringBuilder sb = new StringBuilder();
      int now;
      while(!queue.isEmpty()){
         now = queue.poll();
         sb.append(now).append(' ');

         for(int n:students[now]){
            if(--count[n]==0) queue.offer(n);
         }
      }

      System.out.println(sb);
   }
}

---

3. 결과

직전에 풀었던 음악프로그램보다 조금 더 쉬운 버전이었다.