[백준 10431] 줄세우기 (C++)

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

문제

---

초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.

하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.

우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.

• 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
• 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.

이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.

아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?

 

입력

---

첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.

각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.

20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.

모든 테스트 케이스는 독립적이다.

 

출력

---

각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.

 

문제 풀이

---

구현 문제.

 

문제 그대로 입력 순서대로 구현해주면 된다. 자료구조 중간에 데이터가 삽입되어야 하므로 리스트를 사용한다.

현재 서있는 줄을 표현한 리스트를 처음부터 끝까지 탐색하며 중간에 현재 설 학생의 키보다 큰 학생이 있다면 그 학생 이전에 서도록 insert()를 이용하여 중간에 삽입한다. A(=키 큰 학생 중 가장 앞에 있는 학생)부터 마지막 학생까지는 한 발씩 뒤로 물러서게 되므로 A를 가리키는 iterator와 리스트의 end까지의 거리가 해당 학생을 줄에 넣었을 때 물러난 걸음 수가 된다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int P, T;
	cin >> P;
	for (int p = 0; p < P; p++)
	{
		cin >> T;
		int* arr = new int[20];
		int answer = 0;
		list<int>::iterator it;
		list<int> ls;
		for (int i = 0; i < 20; i++)
		{
			cin >> arr[i];
		}
		ls.push_back(arr[0]);
		for (int i = 1; i < 20; i++)
		{
			for (it = ls.begin(); it != ls.end(); it++)
			{
				if (arr[i] < *it)
				{
					answer += distance(it, ls.end());
					ls.insert(it, arr[i]);
					break;
				}
			}
			if (it == ls.end())
			{
				ls.push_back(arr[i]);
			}
		}
		cout <<T<<" " << answer << "\n";
	}
	return 0;
}