소프티어 교차로

문제

풀이

1. 큐를 이용한 구현 문제

2. 4개의 큐를 만들고 각 큐에 차량의 진입 시간과 교차로 정보를 모두 넣어둔다.

3. cur 이라는 시간변수를 가지고 시간의 흐름에 따라 시뮬레이션 하면서 움직일 수 있는 차들을 움직여준다.

4. t의 범위가 10억이므로 모든 교차로에서 차가 아직 들어오지 않은 경우는 시간을 4개의 교차로중 가장 빨리 들어오는 차의 시간으로 당겨주어야 한다. (시간초과를 피하기 위해)

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
queue<pair<int,int>> q[4];


int conv(char w) {
	switch (w) {
	case 'A':
		return 0;
	case 'B':
		return 1;
	case 'C':
		return 2;
	case 'D':
		return 3;
	default:
		return -1;
	}
}

int main() {
	
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int t;char w;
		cin >> t >> w;
		w = conv(w);
		q[w].push({ i,t });
	}


	vector<pair<int, int>> ans;
	for (int cur = 0;; cur++) {
		vector<int> emp;
		int check = 0,check2=0;
		int least = 1000000001;

		for (int i = 0; i < 4; i++) {
			if (q[i].empty()) {
				emp.push_back(i);
				check++;
				continue;
			}

			int inTime = q[i].front().second;
			if (cur < inTime) {
				emp.push_back(i);
				check2++;
				least = min(least, inTime);
			}
		}

		//큐가 전부 0 or 데드락
		if (check == 4 || emp.size() == 0) {
			if (emp.size()==0) {
				for (int i = 0; i < 4; i++) {
					while (!q[i].empty()) {
						int idx = q[i].front().first;
						q[i].pop();
						ans.push_back({ idx,-1 });
					}
				}
			}
			break;
		}

		for(int i=0;i<emp.size();i++){
			int l = (emp[i] + 1) % 4;
			if (q[l].size() != 0) {
				if (q[l].front().second <= cur) {
					int idx = q[l].front().first; q[l].pop();
					int out = cur;
					ans.push_back({ idx,out });
				}
			}
		}


		if (check + check2 == 4) {
			cur = least-1;
		}
	}

	sort(ans.begin(),ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i].second<<'\n';
	}

}

후기

요즘 알고리즘 안풀었다고 되게 오래걸렸다..