[알고리즘] 백준 1138 한줄로 서기 실버2 Java

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

1138번: 한 줄로 서기

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] arr = new int[n];

        for(int i=0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        LinkedList<Integer> lList = new LinkedList<>();
        for(int i=n; i >= 1; i--){
            int position = arr[i-1];
            lList.add(position, i);
        }
        sc.close();

        lList.forEach(val ->
                System.out.print(val + " "));


    }
}

1. 풀이 

 주어진 배열 뒤부터 탐색해서 LinkedList활용해서 넣어준다.

(ArrayList도 사용해도된다. 하지만 ArrayList는 삽입 이후 배열을 모두 뒤로 밀어야 하기때문에 비효율적)

 

( 2 1 1 0 ) ->

 1. 4번째 를 0번 인덱스 삽입 ( 4 )

 2. 3번째를 1번 인덱스 삽입 (4 3 )

3. 2번째를 1번 인덱스 삽입 ( 4 2 3)

4. 1번째를 2번 인덱스 삽입 ( 4 2 1 3)