[백준/Java] 1138번 한 줄로 서기

문제

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

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

---

문제이해

• 사람 N명 (키 = 1 ~ N, 중복 없음)
• 키 1인 사람부터 N인 사람까지, 본인보다 키 큰 사람이 왼쪽에 몇 명 있었는지 기억

이 기억 정보를 바탕으로 정확한 줄 서기 순서를 구하는 문제

---

문제 풀이 방법

1. 사람 수 N을 입력 받고, 각 사람이 기억하는 값(왼쪽 큰 사람 수)을 배열에 저장
2. 키 1부터 N까지 반복하면서, 그 사람이 기억하는 값(왼쪽 큰 사람 수)에 해당하는 위치에 ArrayList에 삽입
   1. 키가 작은 사람부터 넣어야 왼쪽에 이미 들어가 있는 키 큰 사람의 수를 판단할 수있음

---

💡 키가 작은 사람부터 넣어야하는 이유

키가 작은 사람 입장에서 자신보다 키가 큰 사람의 수를 기억하고 있음

큰 사람은 작은 사람에게는 영향이 없기 때문에

큰 사람 부터 자리배치를 하면 작은 사람이 들어와도 큰 사람의 위치가 변하지 않는 문제 발생….→ 이래서 처음에 에러남

---

코드

import java.util.ArrayList;
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(); // 배열 초기화
        }

        ArrayList<Integer> line = new ArrayList<>(); // 최종 줄 배열

        // 키가 작은 사람부터 (1 ~ N) 넣는다.
        for (int height = N; height >= 1; height--) {
            // arr[height-1] : 이 사람보다 큰 사람이 왼쪽에 몇 명 있었는지
            line.add(arr[height - 1], height);
        }

       for (int person : line) {
            System.out.print(person + " ");
        }
    }
}```