[백준] 1138번: 한 줄로 서기 (Java)

1. 문제설명

N명의 사람들은 한 줄로 서고, 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 구한다.

• 시간 제한: 2초
• 메모리 제한: 128MB

 

2. 접근 방식

• 줄을 나타내는 배열을 생성한다.
• 키 작은 사람부터 차례로:
  • 자신보다 키 큰 사람이 몇 명 있는지 입력받음
  • 그 숫자만큼 빈자리 확보
  • 그 자리에 해당하는 사람을 배치
• 배열 순서대로 출력한다.

 

3. 최종 코드

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

public class Main 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] line = new int[n]; // 줄 배치 저장

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            int cnt = Integer.parseInt(st.nextToken()); // 자신보다 키 큰 사람 수
            for(int j=0; j<n; j++) {
                // cnt가 0이고, 현재 위치가 비어있으면
                if(cnt == 0 && line[j] == 0) {
                    // 해당 자리에 배치
                    line[j] = i + 1;
                    break;
                } else if(line[j] == 0){ // 현재 위치 비어있으면
                    cnt--; // cnt 감소
                }
            }
        }

        for(int i : line) {
            System.out.print(i+" ");
        }
    }
}