프로그래머스) 올바른 괄호 c++ 풀이

 

문제

https://programmers.co.kr/learn/courses/30/lessons/12909

코딩테스트 연습 - 올바른 괄호

 

괄호들이 string으로 주어졌을 때, 괄호들이 전체적으로 올바른지 확인하는 문제다.

( ( ) ) 은 올바르지만

( ) ( 은 닫히지 않아서 올바르지 않고

( ) ) 은 닫을 게 없는데 닫아서 올바르지 않다.

) ( 은 닫을 게 없는데 닫아서 올바르지 않고, 닫히지 않아서 올바르지 않다.

 

 

내 풀이

가장 먼저, 맨 뒤에 있는 '('를 주목해야 한다는 생각이 들었다.

맨 뒤에 있는 '('는 그 앞에 뭐가 있던지 간에 ')'로 닫혀야 한다.

 

((()(()())) 는 온전한 괄호다.

 

맨 뒤에 있는 '('를 소거해나가면 

((()(()()))) 

((()(()())))

((()(()()))) 

((()(()())))

((()(()())))

((()(()())))

 

그렇게 '('들을 ')'로 닫아 소거해나가면 아무것도 남지 않아야 한다.

 

가장 뒤에 있는 '('를 확인하여 (stack의 top)

 

')'일 때 소거해나가며 (stack의 pop)

 

모두 소거했을 때 stack이 비어있어야 한다. (stack의 empty)

 

')' 를 만나면 가장 뒤에 있는 '(' 삭제

 

이와 같이 전체적인 흐름이 stack이라고 생각되어 stack을 이용하여 풀었다.

 

로직

 

1. 순차적으로 string의 요소들을 탐색한다.

2 - 1. '('일 경우

    3. 스택에 넣는다. (임의로 1을 넣음)

2 - 2. ')'일 경우

    3 - 1. 스택이 비어있지 않다면

        4. 맨 뒤에 ')'를 지운다. 

    3 - 2. 스택이 비어있다면 (지울 ')'이 없다면)

        4. false 리턴

3 - 1. 스택이 비어있는 경우

    true 리턴

3 - 2. 스택이 비어있지 않은 경우

    false 리턴

 

코드

 

#include<string>
#include <iostream>
#include <stack>

using namespace std;

bool solution(string s)
{
    stack<int> S;
    
    for (int i = 0 ; i < s.size(); i++)
    {
        if (s[i] == '(')
            S.push(1);
        else
        {
            if (S.empty())
                return false;
            else
                S.pop();
        }   
    }
    return (S.empty());
    /*
    if (S.empty())
        return true; 
    else
        return false;*/
}

 

다른 사람의 풀이

굳이 STL stack을 사용하지 않고도

stack의 index를 하나의 변수에 저장하여

++ -- 연산을 통해서 구할 수 있었다. (음수로 가면 false. 끝나고도 0이 아니면 false.)

stack의 로직이지만 메모리 공간을 절약하는 풀이이다.

 

STL을 가져오기 전에 간단한 변수로도 풀이가 가능한지에 대해 한 번 더 생각해보아야겠다.