백준 2841번 외계인의 기타 연주 C++

출처 : https://www.acmicpc.net/problem/2841

스택 자료구조를 이용하여 해결할 수 있는 문제이다.

줄이 6개라고 했으니 스택을 담고있는 벡터를 6개 만들고 각각의 줄을 따로 계산하여 해결하였다.

 

줄과 프렛을 입력받았을 때 해당 줄에 멜로디가 없거나 입력받은 프렛이 현재 줄의 멜로디보다 높을 경우에는 프렛을 줄에 넣어주고 cnt를 1 증가시켜주었다.

입력받은 프렛이 줄의 멜로디와 같을 경우에는 손가락을 바꿀 필요가 없으므로 아무 행동도 하지 않았다.

 

입력받은 프렛이 줄의 멜로디보다 작을 경우에는 멜로디가 프렛보다 작거나 같아질 때 까지 손가락을 떼주면서 cnt를 1씩 증가시켜 주었다. 그 후 멜로디가 프렛과 같을 경우에는 아무 행동도 하지 않았고, 멜로디가 프렛보다 작거나 남아있는 멜로디가 없을 경우에는 프렛을 줄에 넣어주고 cnt를 1 증가시켜주었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	vector<stack<int>> v(7);
	
	int n, p, line, p_val;
	cin >> n >> p;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		cin >> line >> p_val;
		if (v[line].empty() || v[line].top() < p_val) {
			v[line].push(p_val);
			cnt++;
			continue;
		}
		if (v[line].top() == p_val) continue;
		if (v[line].top() > p_val) {
			while (v[line].top() > p_val) {
				v[line].pop();
				cnt++;
				if (v[line].empty()) break;
			}
			if (v[line].empty()) {
				v[line].push(p_val);
				cnt++;
			}
			else {
				if (v[line].top() == p_val) {
					continue;
				}
				else {
					v[line].push(p_val);
					cnt++;
				}
			}
		}
	}
	cout << cnt;
};