BOJ) 한 줄로 서기

한 줄로 서기

1138번: 한 줄로 서기

풀이

 

고민하는 시간에 비해 코드가 짧은 문제였다.

처음에는 우선순위 큐에 담아서, 적절한 sorting을 통해 출력하려고 했다.

하지만, 메모리 초과가 떴고 다시 고민했다.

 

주어진 정보들을 우선적으로 배열에 담고, 마지막부터(키가 제일 큰 사람부터) 자신의 왼쪽에 몇명이 있는지를 인덱스로 그 사람을 추가하면 된다는 것을 알았다.

 

문제의 예시를 통해 설명하면 더 쉽게 이해가 될 것 같다.

1	2	3	4
2	1	1	0

 

1~4의 값을 담은 배열을 만들고, 4번 사람부터 값을 조회하면서, 해당 값으로 ArrayList에 인덱스로 집어넣으면 답이 나온다.

 

4-> 0번째 인덱스에 추가    ( 4 )

3-> 1번째 인덱스에 추가    ( 4,3 )

2-> 1번째 인덱스에 추가    ( 4,2,3 )

1-> 2번째 인덱스에 추가    ( 4,2,1,3 )

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] persons = new int[n+1];
        for(int i=1; i<=n; i++) persons[i] = Integer.parseInt(st.nextToken());
        br.close();
        solution(n,persons);
    }

    private static void solution(int n, int[] persons) {
        ArrayList<Integer> line = new ArrayList<>();
        for(int i=n; i>0; i--) {
            line.add(persons[i],i);
        }

        StringBuffer sb = new StringBuffer();
        final String space = " ";
        for(int person : line)  sb.append(person).append(space);
        System.out.println(sb.toString());
    }
}