https://www.acmicpc.net/problem/4949
4949번: 균형잡힌 세상
하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다
www.acmicpc.net
스택을 활용하는 문제
#include <iostream>
#include <stack>
#include <string>
int main()
{
std::string str;
std::stack<char> stack;
while (1)
{
std::getline(std::cin, str, '.'); //.을 만날 때까지 받아오기
std::cin.get(); //개행문자 지우기
str.append(1, '.');
if (str[0] == '.') break; //.하나만 있는 경우 break
int i;
for (i = 0; str[i] != '.'; ++i)
{
//괄호의 여는 부분은 stack에 push
if (str[i] == '(' || str[i] == '[') stack.push(str[i]);
else if (str[i] == ')') //괄호의 닫는 부분의 경우
{
//stack의 top과 짝이 맞지 않을 경우 break
if (stack.empty() || stack.top() != '(') break;
//짝이 맞는 경우 스택에서 빼낸다
else stack.pop();
}
else if (str[i] == ']')
{
if (stack.empty() || stack.top() != '[') break;
else stack.pop();
}
else continue; //괄호 외의 문자는 무시
}
if (stack.empty() && str[i] == '.') std::cout << "yes\n";
else
{
while (!stack.empty()) stack.pop(); //stack 초기화
std::cout << "no\n";
}
}
}
'.' 하나만 들어오는 경우 무한루프 break
'.'까지 string으로 받기
괄호를 여는 부분인 ( , [ 를 만나면 스택에 push하고, 닫는 괄호를 만난 경우 스택의 top을 확인한다.
스택의 top이 괄호의 여는 부분이면 pop하고 루프 실행 계속
스택의 top이 괄호의 여는 부분이 아니거나 스택이 비었을 경우 for 루프를 break한다.
'Computer > 알고리즘&백준' 카테고리의 다른 글
[백준][C++] 요세푸스 문제 0 (0) | 2022.12.01 |
---|---|
[백준][C++] 1874 스택 수열 (0) | 2022.11.29 |
[백준][알고리즘][C++] 2750 수 정렬하기, 버블 정렬, 삽입 정렬 (0) | 2022.11.19 |
[백준][C++] 2738 행렬 덧셈 (0) | 2022.11.16 |
[백준] [C++] 11729 하노이 탑 이동 순서 (0) | 2022.11.15 |