1138 한 줄로 서기

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

1138번: 한 줄로 서기

간단해보이지만 헷갈려서 결국 정답을 참고한 문제다.

문제의 핵심은 입력받은 상대 순서, 즉 자신의 왼쪽보다 키 큰 사람이 몇 명있는지이다.

상대 순서를 i라 해보자. 가장 큰 사람부터 줄을 서기 시작하면 항상 맨 처음선다. 이후 줄을 서는 사람의 i가 0인지, 1인지에 따라 먼저 선 사람의 왼쪽인지 오른쪽인지가 결정되는 것이다. 또한 그 다음 사람은 i가 0이면 맨 처음, 1이면 중간, 2이면 맨 오른쪽에 서게된다.

이걸 링크드리스트로 잘 나타낼 수 있는데, 삽입이 어느 인덱스든 자유롭기 때문이다.

 

정답 코드

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

public class Main {
    public static int N;
    public static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < arr.length; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        LinkedList<Integer> lines = new LinkedList<>();
        for(int i = N - 1; i >= 0; i--){
            lines.add(arr[i], i + 1);
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < lines.size(); i++){
            sb.append(lines.get(i)).append(" ");
        }
        System.out.println(sb.toString());
    }
}