문제접근
문제 : 백준 3986 (https://www.acmicpc.net/problem/3986)
유형 : stack
A, B로 이루어진 문자열을 N개 입력받는다. 문자열에서 A는 A끼리, B는 B끼리 선을 이어 서로 겹치지 않으면 좋은 단어로 판단한다. 좋은 단어의 개수를 출력한다.
1) strng을 이용해 문자열 입력 받기
2) 겹치지 않고 선이 그어지려면 문자열의 중심 부분부터 짝꿍이 만들어져야 한다
3) 짝꿍이 있는 문자는 문자열에서 무시해도 된다
-> 단어를 stack으로 받아서 이전 문자와 동일한지 비교하여 짝꿍을 찾는다
제출코드
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
int n, count = 0;
string str;
stack<char> s;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> str;
if (str.length()%2 == 1) continue;
for (char c : str) {
if (!s.empty() && s.top() == c)
s.pop();
else s.push(c);
}
if (s.empty()) count++;
while(!s.empty()) s.pop();
}
cout << count << endl;
return 0;
}문제 해결
- 처음 구현시에는 A와 B를 구분하여 스택을 만들어 두개의 스택 상태를 매번 확인하여 문자열을 검사하였다. 구현 중에 단순히 짝꿍을 찾아주면 되는 문제인데 너무 복잡하게 로직을 짜고 있다는게 느껴져서 처음부터 다시 구현했다. 이전에 구현했던 계산기 괄호 입력과 동일한 문제라는 것을 깨닫고 하나의 stack으로 상태와 top()을 확인하여 짝꿍을 확인할 수 있었다.
- range-based for loop (범위 기반 for 루프)
c++ 11부터 도입된 범위 기반 for 루프를 통해 좀 더 간단하게 모든 요소를 확인할 수 있다.
오늘의 회고
시간 내로 문제를 해결해보자.
