[백준] S2 1138번 한 줄로 서기 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1138번: 한 줄로 서기

[문제] 

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

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

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

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

[입력]

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

[출력]

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

 

 

---

[풀이]

1. 먼저 1의 위치를 입력받은 값에 맞게 고정시켜준다.

2. 그 후, 2부터 n까지 반복을 하면서 각 수마다 빈칸의 개수 + 1이 되는 위치에 입력해준다.

3. 결과를 출력해준다.

[접근]

1. 어떤 식으로 접근하면 될까 생각하다가 처음에 값이 1부터 n까지 순서대로 주어진다는 것을 확인했다.

2. 1의 자리를 고정시켜두고 다음 수부터 왼쪽에 빈칸의 개수를 세서 해당 위치에 값을 넣어주면 되겠다는 생각을 하였다.

3. 2.의 방법이 된다고 생각했던 이유는 수는 점점 큰 수가 입력이 되므로 현재 빈칸의 개수에 맞게 입력을 해주어도 다음 수를 입력할 때 문제가 되지 않기 때문이다.

[코드]

package BOJ_silver;

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

public class Main_S2_1138 {
	static int n;
	static int[] arr;
	static int first;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		first = Integer.parseInt(st.nextToken());
		
		arr[first] = 1; // 1이 들어갈 위치 고정
		
		for (int i = 1; i < n; i++) {
			// 1이후의 숫자들이 왼쪽에 몇개가 있는지에 대한 값을 입력받기
			int num = Integer.parseInt(st.nextToken());
			// 위치를 확인하기 위한 변수
			int check = 0;
			
			// 배열의 처음부터 탐색			
			for (int j = 0; j < n; j++) {
				// 만약 arr[j]가 0이라면 check를 증가
				// check는 해당 숫자의 왼쪽에 있는 0으로 비어있는 칸의 개수
				if (arr[j] == 0) { 
					check++;
				}
				// check가 입력받은 숫자 + 1
				// 작은 숫자부터 들어가기 때문에
				// 왼쪽에 빈칸이 num의 갯수와 같다면
				// 그 다음으로 오는 빈칸에 현재 숫자를 넣으면 된다.
				if (check == num + 1) {
					arr[j] = i + 1; // i+1인 이유는 2부터가 아닌 1부터 반복문을 시작했기 때문
					break;
				}
			}
		}

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