[BOJ] #2605 - 줄 세우기

※ 문제에 대한 저작권은 BAEKJOON ONLINE JUDGE에 있습니다.

💡 출처

---

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

2605번: 줄 세우기

 

💡 문제

---

[설명]

점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다.

그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 먹게 된다.

어떻게 하면 이러한 상황을 바꾸어 볼 수 있을까 고민하던 중 선생님이 한 가지 방법을 내놓았다. 그 방법은 다음과 같다.

학생들이 한 줄로 줄을 선 후, 첫 번째 학생부터 차례로 번호를 뽑는다.

첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다.

두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다.

0번을 뽑으면 그 자리에 그대로 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다.

세 번째로 줄을 선 학생은 0, 1 또는 2 중 하나의 번호를 뽑는다.

그리고 뽑은 번호만큼 앞자리로 가서 줄을 선다.

마지막에 줄을 선 학생까지 이와 같은 방식으로 뽑은 번호만큼 앞으로 가서 줄을 서게 된다.

각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

예를 들어 5명의 학생이 줄을 서고, 첫 번째로 줄을 선 학생부터 다섯 번째로 줄을 선 학생까지 차례로 0, 1, 1, 3, 2번의 번호를 뽑았다고 하자, 첫 번째 학생부터 다섯 번째 학생까지 1부터 5로 표시하면 학생들이 줄을 선 순서는 다음과 같이 된다.

• 첫 번째 학생이 번호를 뽑은 후 : 1
• 두 번째 학생이 번호를 뽑은 후 : 2 1
• 세 번째 학생이 번호를 뽑은 후 : 2 3 1
• 네 번째 학생이 번호를 뽑은 후 : 4 2 3 1
• 다섯 번째 학생이 번호를 뽑은 후 : 4 2 5 3 1

따라서 최종적으로 학생들이 줄을 선 순서는 4, 2, 5, 3, 1이 된다.

줄을 선 학생들이 차례로 뽑은 번호가 주어질 때 학생들이 최종적으로 줄을 선 순서를 출력하는 프로그램을 작성하시오.

 

💡 아이디어

---

첫 번째 학생은 무조건 처음 자리를 차지하게 되니까 넘어간다.

두 번째 학생부터는 뽑은 수에 따라 이동하게 되는 자리를 비워두고 기존 배열에 있던 자리는 뒤로 밀어낸다.

이 과정을 반복하면 최종적인 순서를 구할 수 있다.

 

💡 소스코드

---

package BOJ;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_P2605_줄_세우기 {
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./BOJ_INPUT/BOJ_P2605_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		StringTokenizer sz = new StringTokenizer(br.readLine());
		
		int[] line = new int[T];
		
		for(int i = 0; i < T; i++) {
			line[i] = i + 1;
			int change = Integer.parseInt(sz.nextToken());
			if(change != 0) {
				int temp = line[i];
				for(int j = i; j > i - change; j--) 
					line[j] = line[j - 1];
				line[i - change] = temp;
			}
		}
		
		for(int i = 0; i < T; i++)
			System.out.print(line[i] + " ");
	}
}

 

💡 결과

---