[BOJ] 1138 한 줄로 서기 (Java)

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

 

<초기 아이디어>

처음엔 순서대로 주어진 위치만큼 앞에 자리를 남겨두고 저장하고, 기존 수와 비교하며 뒤로 밀고 넣으면 되겠다하고 구현 했다.

하지만 그렇게 하니 예제 4에서 결과값이 6 2 3 4 5 7 1 이 나왔다.

<문제>

작은 키부터 넣으면 앞에 큰 키의 개수를 제대로 고려하지 못하는 것이었다.

 

<변경 아이디어>

그래서 큰 키부터 넣어야 된다는 것을 깨달았다.

1. 큰 키서부터 주어진 위치만큼 앞에 남겨두고 위치시킨다.

2. 만약 해당 자리에 값이 이미 들어있다면 해당 값은 무조건 더 큰 값이 있을 것이므로 뒤로 쭉 밀고, 지금 값을 자리에 위치시킨다.

3. 그렇게 위치시킨 값을 출력하면 끝!

 

<제출 코드>

package BOJ.Greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1138_한줄로서기 {

    static int n;
    static String[] arr;
    static int[] ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = br.readLine().split(" ");

        ans = new int[n];
        for(int i=n-1; i>=0; i--){
            int idx = Integer.parseInt(arr[i]);
            if(ans[idx] == 0) ans[idx] = i + 1;
            else{
                for(int j=n-1; j>idx; j--){
                    ans[j] = ans[j-1];
                }
                ans[idx] = i + 1;
            }
        }

        for(int i=0; i<n; i++){
            System.out.print(ans[i] + " ");
        }
    }
}