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

[문제 바로 가기] - 한 줄로 서기

💡 접근 방식

예제 1번을 보고 처음엔 왼쪽에 선 자기보다 큰 사람 수 = 순서라고 생각하여 풀이했는데 예제 4번에서 걸렸다. 내가 생각한 풀이로는 예제 4번에서 6 2 3 4 5 7 1가 나오는데 이는 5번째 사람보다 큰 사람이 왼쪽에 2명이라는 입력과 맞지 않다.
따라서 아래의 블로그를 참고하여 풀이해보았다.
https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-1138%EB%B2%88-%ED%95%9C-%EC%A4%84%EB%A1%9C-%EC%84%9C%EA%B8%B0-java

왼쪽에 나보다 큰 사람의 수가 0이고 자리에도 아직 아무도 없다면 그 자리에 넣는다. 이때, i는 키 순서 인덱스이고 index는 들어갈 자리다.
만약 아직 자리에 아무도 없지만 나보다 큰 사람이 있다면 index ++하고 arr[i]-- 해준다. 자리를 한 칸 오른쪽으로 옮겼으므로 arr[i]--를 해주는 것이다.

풀이

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());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] arr = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int seat[] = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			int index = 1;
			while (true) {
				if (arr[i] == 0 && seat[index] == 0) {
					seat[index] = i;
					break;
				} else if (seat[index] == 0) arr[i]--;
				index++;
			}
		}
		
		for (int i = 1; i <= N; i++) {
			System.out.print(seat[i] + " ");
		}
	}
}