[BOJ S2][#그리디]1138번 한 줄로 서기

한 줄로 서기 성공

 

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

4
2 1 1 0

예제 출력 1 복사

4 2 1 3

예제 입력 2 복사

5
0 0 0 0 0

예제 출력 2 복사

1 2 3 4 5

예제 입력 3 복사

6
5 4 3 2 1 0

예제 출력 3 복사

6 5 4 3 2 1

예제 입력 4 복사

7
6 1 1 1 2 0 0

예제 출력 4 복사

6 2 3 4 7 5 1

 

📝 접근법

전형적인 그리디 알고리즘이다. 

7
6 1 1 1 2 0 0

 

해당 입력을 예를 들어보자 

첫번째 키가 1인 사람은 앞에 6명이 있다 즉 앞에 큰 사람이 6명이 되어야 한다.

X X X X X X 1

 

두번째 키가 2인 사람은 앞에 1명이 있다 즉 앞에 큰 사람이 1명이 되어야한다. 그러나 앞으로 들어올 사람은 

무조건 자기보다 크기 때문에 2번째 자리가 된다.

X 2 X X X X 1

 

세번째 키가 3인 사람은 앞에 1명이 있다. 즉 앞에 큰 사람이 1명이 되어야한다. 그래서 2번째 자리인데 2번째 자리는 

이미 사람이 있으므로 그 다음 자리로 가면 된다.

X 2 3 X X X 1

 

네번째 키가 4인 사람은 앞에 1명이 있다. 즉 앞에 큰 사람이 1명이 되어야한다. 그래서 2번째 자리인데 2번째, 3번째 자리는 이미 사람이 있으므로 다음 자리로 가면 된다.

X 2 3 4 X X 1

 

다섯번째 키가 5인 사람은 앞에 2명이 있다. 즉 앞에 큰 사람이 2명이 되어야 한다. 앞에 큰 사람이 2명이 올 수 잇는 것은 앞에 남아잇는 2칸을 제외한 다음 칸으로 가야한다.

X 2 3 4 X 5 1

 

여섯번째 키가 6인 사람은 앞에 아무도 없다 그러므로 첫번째 자리에 오면 된다.

6 2 3 4 X 5 1

 

일곱번째 키가 7인 사람은 앞에 아무도 없다 그러므로 첫번째 자리이나  1, 2, 3, 4 자리 모두 차있으므로 5번째 가면 된다.

6 2 3 4 7 5 1

 

쉽게 이해해보자면 처음에 들어오는 입력은 자기보다 앞에 있는 빈칸의 수를 의미한다.

첫번째 키가 1인 사람은 앞에 빈칸이 6개였으므로 7번째에 갔고 

마지막 키가 7인 사람은 앞에 빈칸이 0개 였으므로 빈칸 중에 제일 앞 자리에 들어갔다.

 

🚩풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim()); // 사람의 수 입력
        StringTokenizer st = new StringTokenizer(br.readLine()); // 각 사람이 기억하는 정보 입력
        
        int[] tallerCount = new int[n];
        for (int i = 0; i < n; i++) {
            tallerCount[i] = Integer.parseInt(st.nextToken());
        }

        int[] result = new int[n];

        // 각 사람이 자신이 기억하는 사람의 수만큼 위치를 찾아서 result 배열에 삽입
        for (int i = 0; i < n; i++) {
            int count = tallerCount[i]; // 자신보다 큰 사람의 수
            for (int j = 0; j < n; j++) {
                if (result[j] == 0) { // 아직 배정되지 않은 위치일 때
                    if (count == 0) {
                        result[j] = i + 1; // i+1은 실제 사람의 번호 (1부터 시작)
                        break;
                    }
                    count--;
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(result[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

 

 

이번에도 핵심 코드만 봐보자

        // 각 사람이 자신이 기억하는 사람의 수만큼 위치를 찾아서 result 배열에 삽입
        for (int i = 0; i < n; i++) {
            int count = tallerCount[i]; // 자신보다 큰 사람의 수
            for (int j = 0; j < n; j++) {
                if (result[j] == 0) { // 아직 배정되지 않은 위치일 때
                    if (count == 0) {
                        result[j] = i + 1; // i+1은 실제 사람의 번호 (1부터 시작)
                        break;
                    }
                    count--;
                }
            }
        }

위의 코드처럼 앞에 빈칸의 갯수로 위치를 정하는 것을 볼 수 있다.