10주차 구현 : 문제 2

✔ BOJ_1138

해당 문제 푸는 아이디어가 생각이 안나서ㅠㅠ 꽤나 고생했습니다. 그러던 도중 제일 키가 큰 사람부터 배치하면 보다 쉽다는 힌트를 얻게 되었고..! 이를 기준으로 풀이를 하였습니다.

// 2 1 1 0
// [0 1 2 3 ]
// 4 2 3 1

// 5 4 3 2 1 0
// [ 0 1 2 3 4 5 ]
// 6 5 4 3 2 1

// 6 1 1 1 2 0 0
// [ 0 1 2 3 4 5 6 ]
// 6 2 3 4 7 5 1

요런 로직으로, 키가 가장 큰 사람을 linkedlist에 추가해놓고 그 다음 키 큰 사람이 왼쪽에 키 큰 사람이 1이면 가장 큰 사람 바로 뒤에 넣기, 0이면 가장 큰 사람 앞에 넣기 하는 식으로 해결하면 됩니다. 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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));
        // N명의 사람들은 각각이 자기보다 큰 사람이 왼쪽에 몇 명이 있었는지만을 기억한다.
        int n = Integer.parseInt(br.readLine());
        // 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에
        // 몇명이었는지 주어진다.
        LinkedList<Integer> lst = new LinkedList<>();
        int[] input = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1;i<n+1;i++){
            input[i] = Integer.parseInt(st.nextToken());
        }

        // '키가 큰 사람 자리부터 고정하라는 힌트'
        for(int i=n;i>=1;i--){
//            if(input[i] > lst.size()) lst.add(i);
//            else{lst.add(input[i], i);}
            lst.add(input[i], i);
        }
        // 2 1 1 0
        // [0 1 2 3 ]
        // 4  2 3 1

        // 5 4 3 2 1 0
        // [ 0 1 2 3 4 5 ]
        //   6 5 4 3 2 1

        // 6 1 1 1 2 0 0
        // [ 0 1 2 3 4 5 6 ]
        //   6 2 3 4 7 5 1

        for (Integer integer : lst) {
            System.out.print(integer+" ");
        }

    }
}