백준 1138 한 줄로 서기 Java

그리디 문제에서 만난 한 줄로 서기 문제이다.

N제한이 10인 걸보고 백트래킹이나, 순열로 완전 탐색을 할까 고민했지만

그리디적인 해법으로 풀어보려고 노력했다.

 

문제를 간단히 설명하면

N명의 사람이 있을 때 앞에 자기보다 키 큰 사람이 몇 명 있는지

키가 1인 사람부터 N인 사람까지 주어진다.

 

꽤 오랜 시간 고민했지만

해답은 무척 간단했다.

키가 큰 순으로 생각하면 된다.

 

4

2 1 1 0으로 주어졌을 때

키가 큰 순으로 입력받은 키 대로 ArrayList에 삽입해주면 된다.

 

키가 4인 사람 -> 0

0번째에 삽입 -> [4]

 

키가 3인 사람 -> 1

1번째에 삽입 -> [4, 3]

 

키가 2인 사람 1

1번째에 삽입 -> [4, 2, 3]

 

키가 1인 사람 2

2번째에 삽입 -> [4, 2, 1, 3]

 

생각해내기는 꽤 어려웠지만 해답은 무척 간단하다.. 코드 또한 간단하다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] tall = new int[n+1];
        List<Integer> ans = new ArrayList<>();
 
        for(int i=1; i<=n; i++) {
            tall[i] = scan.nextInt();
        }
 
        for(int i=n; i>=1; i--) {
            ans.add(tall[i], i);
        }
 
        for(int k : ans) {
            System.out.print(k+" ");
        }
    }