[Baekjoon Online Judge] 1138번: 한 줄로 서기

[Baekjoon Online Judge] 1138번: 한 줄로 서기

1138번: 한 줄로 서기

 처음 문제를 읽는데 이해가 잘 되지 않았다. 입력에 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다고 한다. 그 말은 즉 키의 오름차순으로 서있다는 의미로 받아들여지는 것인지 헷갈렸다.

 

 예제를 기준으로 보면 2 1 1 0 순이다. 그렇기 때문에 키가 큰 순서로 섯다고 가정하고 풀이를 진행하였다. 다른 사람의 풀이를 참고하여 총 두 가지 방법으로 풀이하였다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Baekjoon1138 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bufferedReader.readLine());
        String[] inputSplit = bufferedReader.readLine().split(" ");
        List<Integer> heights = new ArrayList<>();

        for (int i = n; i >= 1; i--) {
            int heightNo = Integer.parseInt(String.valueOf(inputSplit[i - 1]));
            heights.add(heightNo, i);
        }

        for (Integer height : heights) {
            bufferedWriter.write(height + " ");
        }

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 첫 번째 풀이는 ArrayList를 활용하여 역순으로 키가 큰 순섷로 값을 넣어가며 중복되는 index, 즉 heightNo가 나오면 자연스럽게 밀리게 된다. 

 

 과정을 간단하게 디버깅 해보았다.

 

4
2 1 1 0
----------
4 
4 3 
4 2 3 
4 2 1 3 

 

for (int i = n; i >= 1; i--) {
    int heightNo = Integer.parseInt(String.valueOf(inputSplit[i - 1]));
    heights.add(heightNo, i);
}

 

 2, 1, 1, 0을 역순으로 0번 index에 4를 넣는다. 그 다음 1번 index에 그다음 큰 3을 넣는다. 1번 index에 그다음 키 2를 넣는다. 그렇게 되면 3은 먼저 list에 포함되었기 때문에 밀려나게 되서 4, 2, 3 순서가 된다. 마지막으로 2번 index에 가장 작은 1을 넣게 되면 최종적으로 4 2 1 3을 얻을 수 있다. 이것은 입력으로 들어온 왼쪽의 키가 큰 사람의 수의 조건도 맞는 것을 알 수 있다.

---

 또 다른 풀이로는 int 배열을 활용하여 left를 하나씩 줄여가며, 즉 왼쪽에 있는 사람을 하나씩 줄여가며 비어있는 배열에 값을 채워갔다.

 

import java.io.*;

class Baekjoon1138_2 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bufferedReader.readLine());
        String[] inputSplit = bufferedReader.readLine().split(" ");
        int[] heights = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int leftNo = Integer.parseInt(inputSplit[i - 1]);
            for (int j = 1; j <= n; j++) {
                if (leftNo == 0 && heights[j] == 0) {
                    heights[j] = i;
                    break;
                } else if (heights[j] == 0) {
                    --leftNo;
                }
            }
        }

        for (int i = 1; i < heights.length; i++) {
            bufferedWriter.write(heights[i] + " ");
        }

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

References.

백준 1138 한 줄로 서기 Java

[알고리즘] 백준 1138 한 줄로 서기 -그리디- 자바