[Java] 백준 1138 : 한 줄로 서기

문제 링크

1.

어떻게 풀지 조금 고민하다가 문제에서 $N$이 10 이하의 자연수라고 하여서 몇 가지 예를 적어보고 규칙을 찾으면 풀 수 있을 것이라 생각했다.

 

한 5개 정도 직접 써보며 컴퓨터의 입장에서 어떻게 풀지 고민하였더니 풀렸다.

 

정답률 $56\%$의 문제로 난이도가 다소 낮은 문제이다.

 

 

2.

나는 이 예제를 기준으로 문제를 풀었다.

 

input

5

3 3 0 1 0

 

output

3 5 4 1 2

 

 

1. 1번보다 키가 큰 사람의 수가 3이라면 위치가 3일 수 밖에 없다. (arr인덱스의 0부터 계산)

arr

0 0 0 1 0

 

2. 2번보다 키가 큰 사람의 수가 3이라면 arr 인덱스의 0부터 3개의 빈칸을 두어야 한다.

왜냐하면, 3개의 빈칸에 2번보다 키가 큰 사람을 세워야 하기 때문이다.

arr

0 0 0 1 2

 

3. 3번보다 키가 큰 사람의 수가 0이라면 이 사람은 0번째 인덱스에 서 있을 것이다.

arr

3 0 0 1 2

 

4. 4번보다 키가 큰 사람의 수가 1이라면 1개의 빈칸을 두어야 한다.

왜냐하면, 1개의 빈칸에 4번보다 키가 큰 사람을 세워야 하기 때문이다.

arr

3 0 4 1 2

 

5. 5번보다 키가 큰 사람의 수는 0일 수밖에 없다. 빈칸에 세우면 된다.

arr

3 5 4 1 2

 

 

3.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n];

        arr[sc.nextInt()] = 1;

        for (int i = 1; i < n; i++) {
            int record = sc.nextInt();
            int check = 0;

            for (int j = 0; j < n; j++) {
                if (arr[j] == 0) {
                    check++;
                }
                if (check == record + 1) {
                    arr[j] = i + 1;
                    break;
                }
            }
        }

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

 

 

4.

none