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

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

1138번: 한 줄로 서기

 

구현문제로, 해결법을 생각해내기가 조금 어려웠다..

ArrayList iint배열을 만들어서  넣는 방식으로도 도전해봤는데 시간초과가 발생하였다..

결국 int배열로, 입력 받을때마다 빈자리는 양보하면서 자리 배치를 하였다.

 

왼쪽에 2명 있다는 입력을 받으면, 

-> 1번째 자리가 비어있다면 한명에게 자리 양보하니까 왼쪽 (현재 왼쪽 인원수 2) -1 

     2번째 자리도 비어있다면 또 양보하니까 (현재 왼쪽 인원수 1) -1

     3번째 자리가 비어있다면 현재 왼쪽 인원수는 0이나까 이 자리가 바로 해당 사용자의 자리

     만약, 3번째 자리가 차있다면 사용자보다 키가 작은 사람의 자리이니까 다음 자리 번호로 가서 비어있는지 

     확인하기!

 

 

이런식으로 진행해나가면 된다.

 

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());
		int[] arr = new int[n + 1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) { // 현재번호
			int left = Integer.parseInt(st.nextToken());
			for (int j = 1; j <= n; j++) { // 자리 번호
				if (left == 0 && arr[j] == 0) {
					arr[j] = i; // 자리배치
					break;
				} else if (arr[j] == 0) { // 자리 양보
					left--;
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			sb.append(arr[i]).append(" ");
		}

	}

}