[BOJ] 백준 1138. 한 줄로 서기

문제

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

 

---

풀이

 이 문제의 포인트는 큰 숫자부터 LinkedList에 집어넣는다 라고 생각합니다.

 

7
6 1 1 1 2 0 0 :왼쪽의 자기보다 큰 수의 개수
1 2 3 4 5 6 7 :idx

 

예제 4번입니다.

 

여기서 가장 큰 수인 idx=7 부터 LinkedList에 집어넣습니다.

 

LinkedList : 7

 

그리고 idx 6을 집어넣는데 arr값이 0이므로 왼쪽에 큰 값이 없습니다.

 

LinkedList : 6 7

 

idx 5는 arr값이 2입니다. 왼쪽에 자기보다 큰 값이 2개이므로 아래와 같습니다.

 

LinkedList : 6 7 5

 

 이렇게 반복해나가다보면 결국, LinkedList라는 삽입이 용이한 자료구조 특성상, 인덱스를 지정해서 LinkedList에 넣어주면 됩니다. 그리고 이 인덱스는 arr 값입니다. 위 예시처럼 인덱스라는 것이 자기보다 큰 값들의 개수이기 때문입니다.

 

 

 

아래는 소스 코드입니다.

---

소스 코드

import java.util.LinkedList;
import java.util.Scanner;

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> list = new LinkedList<>();
        for(int i = N-1;i>=0;i--){
            int idx = arr[i];
            list.add(idx,i+1);
        }
        for(int i = 0; i<N;i++){
            System.out.print(list.get(i)+" ");
        }
    }
}