2605번 줄 세우기

링크 : 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이 된다.

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

입력

첫째 줄에는 학생의 수가 주어지고 둘째 줄에는 줄을 선 차례대로 학생들이 뽑은 번호가 주어진다. 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다.

출력

학생들이 처음에 줄을 선 순서대로 1번부터 번호를 매길 때, 첫째 줄에 학생들이 최종적으로 줄을 선 순서를 그 번호로 출력한다. 학생 번호 사이에는 한 칸의 공백을 출력한다.

 

 

---

 

풀이

1) 배열에 입력 데이터를 넣어줍니다.

2) 배열을 돌면서 how크기 만큼 line에서 학생을 빼내어 temp에 저장해줍니다.

3) how가 0이되면 학생을 line에 넣어줍니다.

4) temp에서 학생을 순서대로 빼서 line에 다시 넣어줍니다.

5) 최종적으로 입력 배열을 모두 돌았다면 출력을 위한 list를 생성한 뒤, stack.pop()으로 끝에서 부터 채워줍니다.

 

 

step1. 초기화 상황

 

step2. 1번 student 줄 세우기

step3. 2번 student 줄 세우기

 

 

step4. 3번 student 줄 세우기

 

step5. 4번 student 줄 세우기

step6. 5번 student 줄 세우기

step7. 결과 출력 list에 line.pop()으로 채우기

 

구현 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[] how = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for(int i =0;i<N;i++) {
			how[i] = Integer.parseInt(st.nextToken());
		}
		
		int student = 1;
		Stack<Integer> line = new Stack<Integer>();
		Stack<Integer> temp = new Stack<Integer>();
		for(int i =0;i<N;i++) {
			while(how[i]>0) {
				temp.push(line.pop());
				how[i]--;
			}
			line.push(student++);
			while(!temp.isEmpty()) {
				line.push(temp.pop());
			}
				
		}
		
		int[] result = new int[N];
		for(int i = N-1; i>=0;i--) {
			result[i] = line.pop();
		}
		for(int i =0;i<N;i++) {
			bw.write(result[i]+" ");
		}
		bw.flush();
		br.close();
		bw.close();	
	}
}

 

---

 

다른 사람 풀이 

 

방법 1. 

Arraylist로 배열을 구현하고 .add(원하는 index, 값)을 이용하여 숫자를 입력받는 동시에 배열에 삽입

=> 차이점 : 한번 for문을 도는 것으로 정렬이 모두 끝나므로 arrayList를 쓰는 것이 효과적일 듯 하다.

https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-2605%EB%B2%88-%EC%A4%84-%EC%84%B8%EC%9A%B0%EA%B8%B0-%EC%9E%90%EB%B0%94Java

[백준 알고리즘] 백준 2605번 줄 세우기 자바(Java)

 

방법2. 

LinkedList로 배열을 구현하고 .add(원하는 index, 값)을 이용하여 숫자를 입력받는 동시에 배열에 삽입

=> 차이점 : 한번 for문을 도는 것으로 정렬이 모두 끝나므로 arrayList와 동일하게 효과적일 듯 하다.

https://muengx2.tistory.com/4

[JAVA] 백준 2605 줄세우기