[소프티어] - 교차로 C++

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=803 

Softeer

 

간단한 구현 문제였다.

 

처음에는 최소 시간과 최대시간 + 4 만큼 for문을 돌면서 해당 시간에 차가 지나갈 수 있다면 정답배열에 시간을 담아주는 식으로 하려고 했는데, 시간이 최대 10^9 (십억) 이라서 제한시간 2초에 걸려 시간초과가 났었다.

 

그래서 흠 이렇게 해서는 안되겠군 이라는 생각과 함께,

차가 안들어오는 시간대는 패쓰해야겠다는 생각이 들어 해당 코드를 추가시켜 주었더니 통과했다.

 

전반적인 로직은 아래와 같다.

1. A, B, C, D 교차로에 들어오는 차들을 큐에 담아주었다. 나중에 정답배열을 입력받은 순서대로 출력해야 하므로, 입력받은 index와 그리고 들어온 시간을 pair 로 해서 담아주었다.

2. 4개의 큐 중 하나에라도 차가 있는 동안 반복문을 돈다. 교착상태가 된 겨우 탈출해준다.

cur_time 이 현재 시간인데, 각 큐의 맨 앞에 있는 차들의 시간이 cur_time 보다 같거나 작으면 검사 대상이 된다.

검사 대상의 차들의 오른쪽에 차가 있는지 보고, 있으면 true, 없으면 false 로 해주고, 검사가 끝났으면 true 가 된 교차로의 맨 앞 차들을 큐에서 pop하고 answer 벡터에 cur_time 을 저장한다.

만약, A, B, C, D 교차로가 비어있지 않지만, 해당 교차로 맨 앞 차들이 들어온 시간이 모두 cur_time보다 작다면 교착상태로 보고 반복문을 탈출한다.

시간초과를 방지하기 위해서는 cur_time을 갱신해주어야 하는데, A, B, C, D 교차로 맨 앞에 있는 차들이 들어온 시간이 모두 cur_time 보다 크다면, 그 중에서 제일 빨리 들어온 시간으로 갱신해준다.

 

 

전체 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

const int MAX_INF = 1000000001;
int main(int argc, char** argv)
{
	int n;
	int max_t, min_t;
	scanf("%d", &n);

	queue<pair<int, int>> a; // index, time
	queue<pair<int, int>> b;
	queue<pair<int, int>> c;
	queue<pair<int, int>> d;
	vector<int> answer;
	answer.assign(n + 1, -1);

	for(int i = 0; i < n; ++i) {
		int temp;
		char ch;
		scanf("%d %c", &temp, &ch);
		if (ch == 'A') {
			a.push({i, temp});
		} else if (ch == 'B') {
			b.push({i, temp});
		} else if (ch == 'C') {
			c.push({i, temp});
		} else if (ch == 'D') {
			d.push({i, temp});
		}
		if (i == 0)
			min_t = temp;
		else if (i == (n - 1))
			max_t = temp;
	}

	int cur_time = min_t;

	while(!a.empty() || !b.empty() || !c.empty() || !d.empty()) {
		int a_min = MAX_INF;
		int b_min = MAX_INF;
		int c_min = MAX_INF;
		int d_min = MAX_INF;
		if (!a.empty())
			a_min = a.front().second;
		if (!b.empty())
			b_min = b.front().second;
		if (!c.empty())
			c_min = c.front().second;
		if (!d.empty())
			d_min = d.front().second;
		if ((a_min < cur_time) || (b_min < cur_time) || (c_min < cur_time) || (d_min < cur_time)) {
		} else {
			cur_time = min({a_min, b_min, c_min, d_min});
		}

		// 각 큐를 돌아가면서 검사
		bool isA_Possible = false;
		bool isB_Possible = false;
		bool isC_Possible = false;
		bool isD_Possible = false;

		// 교착상태 검사
		bool isA_Stuck = false;
		bool isB_Stuck = false;
		bool isC_Stuck = false;
		bool isD_Stuck = false;

		if (!a.empty()) {
			if(d.empty() && a.front().second <= cur_time) {
				isA_Possible = true;
			}
			if (!d.empty() && d.front().second > cur_time && a.front().second <= cur_time) {
				isA_Possible = true;
			}
			if (!isA_Possible && a.front().second <= cur_time) {
				isA_Stuck = true;
			}
		}
		if (!d.empty()) {
			if(c.empty() && d.front().second <= cur_time) {
				isD_Possible = true;
			}
			if (!c.empty() && c.front().second > cur_time && d.front().second <= cur_time) {
				isD_Possible = true;
			}
			if (!isD_Possible && d.front().second <= cur_time) {
				isD_Stuck = true;
			}
		}
		if (!c.empty()) {
			if(b.empty() && c.front().second <= cur_time) {
				isC_Possible = true;
			}
			if (!b.empty() && b.front().second > cur_time && c.front().second <= cur_time) {
				isC_Possible = true;
			}
			if (!isC_Possible && c.front().second <= cur_time) {
				isC_Stuck = true;
			}
		}
		if (!b.empty()) {
			if(a.empty() && b.front().second <= cur_time) {
				isB_Possible = true;
			}
			if (!a.empty() && a.front().second > cur_time && b.front().second <= cur_time) {
				isB_Possible = true;
			}
			if (!isB_Possible && b.front().second <= cur_time) {
				isB_Stuck = true;
			}
		}
		// 교착상태인지 검사
		if (isA_Stuck && isB_Stuck && isC_Stuck && isD_Stuck)
			break;
		if (isA_Possible) {
			answer[a.front().first] = cur_time;
			a.pop();
		}
		if (isB_Possible) {
			answer[b.front().first] = cur_time;
			b.pop();
		}
		if (isC_Possible) {
			answer[c.front().first] = cur_time;
			c.pop();
		}
		if (isD_Possible) {
			answer[d.front().first] = cur_time;
			d.pop();
		}
		cur_time++;
	}

	for(int i = 0; i < n; ++i) {
		printf("%d\n", answer[i]);
	}
	
	return 0;
}