프로그래머스 : 올바른 괄호 _ C++

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

프로그래머스

#스택 #큐 #lv.2 

 

회고

 

✔ 접근 방법

문제는 앞의 괄호랑 비교를 해서 모든 괄호가 짝이 맞는지 판별하는 것이었다.

처음엔 () 이렇게 짝이 맞아야 하는것을 고려하지 않고 그냥 전의 괄호와 현재 괄호가 일치하지 않을 경우로 생각해서 틀렸었다.

 

해당사항을 해결 하고 4개의 테스트 케이스가 통과했길래 제출을 했지만 3-4개의 테스트 케이스가 실패해서 다시 고민했다.

원인은 만약 앞의 괄호들은 짝이 없지만, 마지막 두개의 괄호가 맞으면 asnwer = true가 되어버려 결국 최종 결과가 true가 되어 실패했던 것이었다. 

따라서 반복문이 끝나고 벡터의 원소 개수를 확인하여 짝이 되지 못한 괄호가 있는지 판별해줬고, 결과는 성공이었다.

 

✔ 코드 수정

이전에 입력했던 짝이 맞지 않는 괄호들을 저장해야 할 자료구조를 처음엔 벡터를 사용해서 저장해줬는데 풀고나니까 해당 원소들은 스택이나 큐로도 저장해줘도 문제없기 때문에 깔끔하게 스택으로도 다시 풀어봤다.

 

삼성 코딩테스트 준비를 위해 백준에서 그래프 문제를 격파하다가 프로그래머스 LV.2 문제를 푸니 확실히 쉽긴 했다. 😊

코드

//벡터 사용
#include <string>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    queue<char> bracket;
    for (int i = 0; i < s.length(); i++) {
        bracket.push(s[i]);
    }

    vector<char> tmp;
    int i = 0;

    while (!bracket.empty()) {
        char cur = bracket.front();
        bracket.pop();
        tmp.push_back(cur);
        if (i != 0 && tmp[i - 1] == '(' && cur == ')') { 
            //짝 맞는 애들 삭제
            tmp.pop_back();
            tmp.pop_back();
            i--;
            answer = true;
            continue;
        }
        i++;
    }

    if (tmp.size() > 0) answer = false;
    return answer;
}

//스택사용
#include <string>
#include <queue>
#include <stack>
#include <iostream>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    queue<char> bracket;
    for (int i = 0; i < s.length(); i++) {
        bracket.push(s[i]);
    }

    stack<char> tmp;
    while (!bracket.empty()) {
        char cur = bracket.front();
        bracket.pop();

        if (!tmp.empty() && tmp.top() == '(' && cur == ')') {
            //짝 맞는 애들 삭제
            tmp.pop();
            answer = true;
            continue;
        }
        tmp.push(cur);
    }

    if (tmp.size() > 0) answer = false;
    return answer;
}