[백준]1138번. 한 줄로 서기

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

---

문제

---

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        boolean[] arr= new boolean[n+1];
        int[] index = new int[n+1];

        st = new StringTokenizer(br.readLine());

        for(int i = 1; i <= n; i++){
            int count = Integer.parseInt(st.nextToken());
            for(int j = 1; j <= n; j++){
                if(!arr[j]){
                    count--;
                    if(count == -1){
                        arr[j] = true;
                        index[j] = i;
                    }
                }
            }
        }
        for(int i = 1; i <= n; i++){
            System.out.print(index[i] + " ");
        }
    }
}

 

문제 풀이 순서는 다음과 같다.

 

1. 사용자 입력을 통해 배열의 크기를 받는다. 이 때 배열은 출력 순서를 저장할 int배열과 키에따른 정보를 저장할 boolean 배열 두개를 선언한다.

 

2. 사용자가 입력해준 값에 따라 탐색을 시작한다. 키가 작은 순서부터 배치하면 된다.( 키가 작은 사람은 이 후 올 사람은 무조건 자신보다 크다는 확신이 있기 때문)

 

3. 자기보다 큰 사람을 왼쪽에 둘 수 있는 자리에 서게 되면서 그 자리는 섰음을 표시하고, int배열에 자기의 키 또한 저장한다.

 

4. 이 후 키가 작은 사람은 마찬가지로 탐색을 진행하지만 값이 true인(자기보다 작은 사람이 이미 서버린 자리)는 제외하고 count를 하여 위치하게 된다.