[BOJ 2605] 줄 세우기

문제

• BOJ 2605
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

차근차근 생각해보면 쉽게 풀리는 문제인데 머릿속으로 계산하려고 하니 난이도에 비해서 오래 걸렸던 문제이다.
배열로 처음 학생들이 가진 번호를 입력받고, 그 크기만큼의 새로운 배열 result를 생성하여 학생들의 번호를 하나씩 뽑을때마다 줄세운 결과를 저장한다. 뽑은 번호만큼 앞으로 가게 되므로 앞으로 가게 될 인덱스부터 현재 뽑힌 학생 끝까지를 오른쪽으로 한칸씩 뒤로 미루면 앞에 세워야할 자리가 비워지고 여기에 현재 학생을 넣으면 된다.

코드

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

//줄세우기
public class Main {
	
	static int[] arr;
	static int[] result; //줄세운 결과
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine()); //학생 수
		arr = new int[num+1];
		result = new int[num+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=num; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		result[1] = 1;
		for(int i=2; i<=num; i++) {
			if(arr[i] == 0) result[i] = i;
			else { //앞으로 이동
				//앞으로 가야 하는 위치
				int go = i-arr[i];
				for(int j=i-1; j>=go; j--) { //앞으로 들어갈 번호부터 뒤로 한칸씩 
					result[j+1] = result[j];
				}
				result[go] = i;
			}
		}
		
		for(int i=1; i<=num; i++) System.out.print(result[i]+" ");
	}
}