(Java) 백준 1138번 - 한 줄로 서기

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

문제

> N명의 사람들은 매일 아침 한 줄로 선다. 
> 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

> 어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 
> 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

> 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. 
> N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

> 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

접근

주어진 좌측에 자신보다 몇명이나 큰 사람이 있는지의 수를 기반으로 오름차순 정렬을 한다.
결과를 저장할 배열에 해당 우선순위 대로 집어넣는데 배열의 각 원소와 비교하며 자기 보다 큰 사람이 나올 때 마다 누적한 cnt(지금까지 오면서 본 나보다 큰 사람의 수)를 보는데 이 cnt가 우선순위와 같다면 해당 인덱스에 집어넣고 아니면 cnt를 누적하며 다음 사람들을 본다.

문제해결

> 총 인원 N과 나보다 큰 사람의 수를 저장할 height List를 배열타입으로 선언한다.
> 배열 안에 해당 사람의 인덱스 번호와, 왼쪽에 있는 더 큰 사람의 수를 쌍으로 저장하기 위해서이다.
> 최종 결과를 저장할 rst배열도 선언해주고 입력을 처리한다.
> height에 인덱스, 왼쪽에있는 큰사람 수를 쌍으로 받고 이를 큰 사람 수 기준 오름차순 정렬한다.
> 이제 반복문으로 모든 사람에 대해 돌면서 나보다 큰 사람의 수를 누적할 cnt와 반복문을 깨줄 flag를 선언한다.
> 현재 따져줄 사람의 정보, 인덱스와 왼쪽에 있는 큰 수를 cur 배열에 잡아와 준다.
> rst배열을 돌며 순서가 파악되어 줄을 세워둔 사람과 비교한다.
> 각 번째의 사람과 비교하며 cur보다 크면 일단 누적된 cnt를 본다.
> 누적된 cnt가 cur이 가진 왼쪽에 있는 더 큰 사람의 수와 같다면 해당 위치에 cur을 넣어주면서 반복문을 깨준다.
> 아니라면 cnt를 누적하고 자신이 들어갈 위치를 탐색한다.
> flag는 앞선 과정에서 자신의 순서가 정해지지 않은, 즉, 줄의 맨 뒤에 들어가야 할 사람을 세워주는 역할을 한다. 

코드

import java.beans.beancontext.BeanContext;
import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    //1138번 한 줄로 서기
    static int N;
    static List<int[]> height;
    static List<Integer> rst;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        height = new ArrayList<>();
        rst = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) height.add(new int[]{i+1, Integer.parseInt(st.nextToken())});
        height.sort((a, b) -> a[1] - b[1]);

        for(int i = 0; i < height.size(); i++) {
            boolean flag = true;
            int cnt = 0;
            int[] cur = height.get(i);
            for(int j = 0; j < rst.size(); j++) {
                if(rst.get(j) > cur[0]) {
                    if(cnt == cur[1]) {
                        rst.add(j, cur[0]);
                        flag = false;
                        break;
                    }
                    cnt++;
                }
            }
            if(flag) rst.add(cur[0]);
        }
        for(int i : rst) System.out.print(i + " ");
    }
}

후기

로직을 생각하는데 생각보다 어려웠고, 이를 구현하는데 자꾸 우선순위가 같은 사람들끼리 순서가 잘못되었다.