[BOJ] 17178 : 줄서기 - travelbeeee

문제 : https://www.acmicpc.net/problem/17178

---

스택 정렬 투포인터

● 대기공간은 마지막에 들어온 사람이 가장 먼저 나갈 수 있으므로, 자료구조 스택을 이용하면 쉽게 구현할 수 있습니다.

● 들어온 입력을 list에 담고, list를 정렬한 배열을 order 라고 하자. 투 포인터를 이용해 list와 order를 동시에 순회하면 된다.

1) list[i] 와 order[j] 가 같다면 입장이 가능한 경우이므로 i와 j를 다음 칸으로 옮겨줍니다.

2) list[i]와 order[j]는 다르지만 stack(대기공간)의 top과 order[j]가 같다면 stack을 pop하고 j 를 다음 칸으로 옮겨줍니다.

3) 그것도 아니라면 대기 공간으로 list[i]를 보내버리고 i를 다음 칸으로 옮겨줍니다.

● 순회가 다 끝나고 아직 stack(대기공간)이 비어있지 않다면 입장이 완료된 것이 아니므로 order 과 비교해가며 한 명씩 입장을 시킵니다. 이때, order[j]와 stack의 top이 다르다면 순서대로 입장한 것이 아니므로 BAD를 출력합니다.

#include<iostream>
#include<string>
#include<stack>
#include<algorithm>
#include<vector>

using namespace std;

bool cmp(string a, string b) {
	if (a[0] < b[0])
		return true;
	else if (a[0] > b[0])
		return false;
	else{
		string temp1 = {}, temp2 = {};
		for (int l = 2; l < a.size(); l++)
			temp1 += a[l];
		for (int l = 2; l < b.size(); l++)
			temp2 += b[l];
		int ntemp1 = stoi(temp1), ntemp2 = stoi(temp2);
		if (ntemp1 < ntemp2)
			return true;
		return false;
	}
}

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

	int N;
	string x;
	vector<string> list;
	vector<string> order;

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < 5; j++) {
			cin >> x;
			list.push_back(x);
			order.push_back(x);
		}

	sort(order.begin(), order.end(), cmp);
	
	bool flag = false;
	int i = 0, j = 0;
	stack<string> s;

	while (i <  5 *N && j < 5 * N) {
		if (list[i] == order[j]){
			i++, j++;
		}
		else if (!s.empty() && s.top() == order[j]){
			s.pop();
			j++;
		}
		else {
			s.push(list[i]);
			i++;
		}
	}
	while (!s.empty()) {
		if (s.top() != order[j]) {
			flag = true;
			break;
		}
		s.pop(), j++;
	}

	if (flag)
		cout << "BAD\n";
	else
		cout << "GOOD\n";
	return 0;
}

---