[자료구조] 백준 문제 풀이 - 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번부터 번호를 매길 때, 첫째 줄에 학생들이 최종적으로 줄을 선 순서를 그 번호로 출력한다. 학생 번호 사이에는 한 칸의 공백을 출력한다.

 

[나의 풀이] (연결리스트 이용)

#include <iostream>
#include <list>
using namespace std;

int main()
{
	list <int> li;
	list <int>::iterator iter=li.begin(); // 출력용
	int student_num;
	cin>>student_num;
	int pick_num;
	
	for(int i=1; i<=student_num; i++)
	{
		cin>>pick_num;
		list <int>::iterator temp=li.end(); // 삽입용
		for(int j=0; j<pick_num; j++)
		{
			temp--; // 애들이 뽑은 숫자 만큼 삽입 위치가 앞으로 당겨짐
		}
		li.insert(temp, i); // 삽입
	}
	
	for(iter=li.begin(); iter!=li.end(); iter++)
	{
		cout<<*iter<<" ";
	}
	cout<<endl;
	return 0;
}

 

[다른사람의 풀이] (배열 이용)

#include <iostream> 
using namespace std; 
int main() 
{ 
	int n, a[100]; 
	int i, j, x; 
    cin >> n; 
    for (i = 0; i < n; i++) 
    { 
    	cin >> x; 
        for (j = i; j > i - x; j--) //x를 뺀 만큼 for문이 실행됨
        { 
        	a[j] = a[j - 1]; // 배열 뒤에서부터 1칸씩 뒤로 땡겨서 새로운 친구가 들어갈 자리 만듬 
        } 
        a[j] = i + 1; //남은 j자리에 값 삽입
    }
    
    for (i = 0; i < n; i++) 
    	cout << a[i] << " "; 
    return 0; 
}

출처: https://twinparadox.tistory.com/224 [Twinparadox Factory]

 

해석 : a[3]을 a[2]로, a[2]를 a[1]로, a[0]을 a[1]로 땡겨서 a[0]에 새로운 녀석을 삽입 (a[j] = i+1)