[백준] 1138: 한 줄로 서기 - JAVA

in Algorithm on 구현

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

풀이

키가 1인사람부터 N인사람이 순서대로 자기보다 큰 사람이 왼쪽에 몇 명 있는지 주어진다.

즉, 0 0 0 0 이렇게 주어지면 1번사람은 왼쪽에 자기보다 큰 사람이 0명 있으므로 첫 번째 자리에 서있는 것이다.

숫자를 받아 for문을 돌면서 자리가 안채워져 있으면 카운트를 하나씩 한다.

자리가 채워져있으면 넘어간다.

카운트가 입력받은 수와 같으면 그 자리에 해당 사람을 위치시키면 된다.

메모리: 15852KB

시간: 144ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] ans = new int[N];
        for (int i = 0; i < N; i++) {
            int cnt = arr[i];
            for (int j = 0; j < N; j++) {
                if (ans[j] != 0) {
                    continue;
                }
                if (cnt == 0) {
                    ans[j] = i + 1;
                    break;
                }
                cnt--;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(ans[i] + " ");
        }

        System.out.println(sb);
    }

}