[BOJ] 1138 한 줄로 서기 (Java)

문제 링크

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

 

문제 이해

개인적으로 무슨 말인지 이해가 안가서 헤맨 문제다. 

간단하게 말하자면, 순서 세우기인데 index번호가 키를 뜻하는 지 몰랐다 (문제에 나와있음에도 불구하고 ㅎㅎ)

 

이 문제는 키가 큰 순서대로 해당하는 order 번호에 넣어주면된다.

고정 리스트를 사용하지 않고 가변 리스트를 사용하면 키큰 아이가 먼저 서고, 키가 작은 아이가 이후에 order에 맞게 섰을 때

order[index]값 자신이 기억하고 있는 "자신보다 키 큰 사람의 수"가 변경되지 않기 때문에 무관하다.

 

이 문제는 ArrayList의 index 개념을 이해했는가 & 응용할 수 있는가를 확인하는 문제같다.

 

예제

7
6 1 1 1 2 0 0

 

풀이 과정

 

 

코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * BOJ_1138_한줄서기
 * N명 사람 -> 한줄
 * 오민식 사람 줄서는 위치 기록함
 * 매일 자기가 기록한거랑 사람 줄 위치랑 맞는 지 확인함
 * 자기보다 큰 사람이 왼쪽에 몇명이 있었는지만 기억한다.
 *
 * */
public class BOJ_1138_한줄로서기 {

    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine().trim());
        st = new StringTokenizer(br.readLine().trim());

        int[] list = new int[N + 1];
        for (int idx = 1; idx < N + 1; idx ++) {
            list[idx] = Integer.parseInt(st.nextToken());
        }
        ArrayList<Integer> order = new ArrayList<>();
        // 키 큰 순서대로 순서에 넣는다
        for (int idx = N  ; idx >= 1; idx --) {
            order.add(list[idx], idx); // 몇번째 순서에 몇번째키인지
        }

        sb = new StringBuilder();
        for (int idx : order) {
            sb.append(idx).append(" ");
        }
        System.out.println(sb.toString());
    }
}