[자료구조] 백준 5525번: IOIOI (C++), 스택을 이용한 트릭

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

5525번: IOIOI

이번 문제 또한 스택을 사용해야 할 거 같다는 확신이 들었다.

하지만, 스택을 이용해서 트릭을 만들어낼 수 있는 능력이 이번 문제의 포인트다.

 

솔루션

"IOIOI"라는 문자열에 n이 1이라면 답은 2가 출력되어야 한다.

내가 만든 트릭은 첫 "IOI"가 발생할 때, 이를 스택에 담고 n이 1인 경우를 만족시켰으므로 하나를 count 한 다음에 두 번만 pop 해서 I(문자열 0번 인덱스)를 남겨두고 "OI"를 스택에 집어넣어서 다시 n이 1인 경우를 만족시켜 총 두 번의 count를 하게 한다.

>> 다음 트릭은 단조 스택(monotonic stack)에서 영감을 받았다.

 

https://draw-code-boy.tistory.com/30?category=962020 

[자료구조] 백준 17298번: 오큰수 (C++), Monotonic Stack (단조로운 스택)

---

소스 코드

#include <iostream>
#include <stack>
using namespace std;

int n, m;
string idx;
stack<char> s;
int result = 0;

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

	for (int i = 0; i < idx.size(); i++) {
		if (s.empty() && idx[i] == 'I') {
			s.push(idx[i]);
		}
		else if (!s.empty() && s.top() != idx[i]) {
			s.push(idx[i]);
		}
		else {
			while (!s.empty()) {
				s.pop();
			}
			if (idx[i] == 'I') {
				s.push(idx[i]);
			}
		}
		
		if (s.size() == 2 * n + 1) {
			result++;
			//cout << i << ' ';
			s.pop();
			s.pop();
		}
	}

	cout << result;
	return 0;
}