[Baekjoon] 1138: 한 줄로 서기

문제

각 index 번째에 있는 사람들의 왼쪽에 자기보다 큰 사람이 몇 명 있는지 주어지면, 각 사람들의 번호를 위치 순서로 출력하는 문제이다.

 

풀이

내 풀이

public class Q1138 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> numbers = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());
        String[] leftCounts = br.readLine().split(" ");

        for (int i = n - 1; i >= 0; i--) {
            int leftCount = Integer.parseInt(leftCounts[i]);

            if (leftCount == 0) {
                numbers.add(0, i + 1);
                continue;
            }

            int count = 0;
            for (int j = 0; j < numbers.size(); j++) {
                if (numbers.get(j) > i + 1) {
                    count++;
                }

                if (count == leftCount) {
                    numbers.add(count, i + 1);
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(numbers.get(i)).append(" ");
        }
        System.out.println(sb);
    }
}

이 문제는 예제가 많아서 풀이가 좀 더 수월했던 것 같다.

일단 결과값들의 공통점을 보면, 마지막 수는 제일 크기 때문에 왼쪽에 아무도 더 큰 사람이 없다는 것이다.

이를 확인하면 이후 풀이가 쉬워진다.

 

위 내용을 활용하기 위해 여기선 먼저 오른쪽부터 탐색했다.

이렇게 하면 필연적으로 다음 값(오른쪽부터 탐색하므로 이전 index 값)의 최댓값은 현재 리스트의 Size의 값이다.

왜냐하면 이미 큰 사람들은 오른쪽부터 탐색하여 리스트에 들어갔기 때문이다.

 

회고

이보다 더 좋은 방법이 생각날 것 같은데 쉽지 않다.

추후에 다시 풀어보고 더 좋은 방법을 생각해봐야겠다.