munjjang9
문짱구의 게임 개발 블로그
Game Programmer

[프로그래머스] 괄호 회전하기

•


Programmers - [월간 코드 챌린지 시즌2] 괄호 회전하기



사용 언어 - C++

소요 시간 - 약 48분



문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/76502



문제 요약

  1. 무작위로 배열된 괄호가 주어짐
  2. 올바른 괄호 문자열의 조건
    • 괄호는 항상 열린 후 닫혀야 함
    • 괄호는 항상 늦게 열린 괄호가 먼저 닫혀야 함
  3. 올바른 괄호 문자열의 조건을 만족했다면 정답++
  4. 문자열 체크가 완료됐다면 가장 왼쪽의 괄호를 가장 오른쪽으로 보내 회전
  5. 문자열 s의 길이만큼 체크
  6. 정답 수 return



최종 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    for(int i = 0; i < s.length(); i++)
    {
        stack<char> par; //괄호가 영어로 parenthesis
        bool bOpened = false;
     
        for(int j = 0; j < s.length(); j++)
        {
            if(s[j] == '[' || s[j] == '{' || s[j] == '(')
            {
                par.push(s[j]);
                bOpened = true;
            }
            else
            {
                bool bCheck = false;
                bCheck |= (s[j] == ']' && par.top() == '[');
                bCheck |= (s[j] == '}' && par.top() == '{');
                bCheck |= (s[j] == ')' && par.top() == '(');
                if(bCheck)
                    par.pop();
            }
        }//for(j)
        
        if(par.empty() && bOpened == true)
            answer++;

        char c = s[0];
        s.erase(s.begin());
        s.push_back(c);
    }//for(i)
    
    return answer;
}



트러블 슈팅

  • 닫히는 괄호를 스택에 넣지 않았기에 괄호가 열리지 않은 상태에서 닫히기만 하면 스택이 비어있는 걸로 처리됨
    • 닫히는 괄호를 스택에 넣고, 이전 주소가 같은 종류의 열리는 괄호라면 두개를 뺌 - X (비효율적으로 생각됨)
    • 열리는 괄호가 최소 하나 이상 존재하는 경우에 정답을 체크하는 쪽으로 넘어갈 수 있도록 함 - O (bool 변수 하나로 처리 가능능)
  • 괄호를 회전 시키는 데 필요한 for문 - 1. 회전 후 괄호를 순회하며 체크해줄 for문 -1.
    • 총 for문이 2개 필요



풀이 절차

  1. s의 사이즈 만큼 반복하는 중, 괄호가 정상적으로 열린 후에 닫혔는지 판단
  2. 늦게 열린 괄호가 먼저 닫혀야 하는 LIFO 구조이기 때문에 스택 자료구조 채택
  3. 올바른 괄호 문자열 조건에 해당하는 경우에 해당 괄호가 닫혔으면 pop으로 해당 괄호를 빼냄
  4. 정상적으로 괄호가 하나 이상 닫히는 경우에만 정답을 체크하는 쪽으로 넘어갈 수 있음
  5. 정답의 조건은 스택이 비어있는 동시에 괄호가 열리는 것이 우선이었던 경우에만(닫히는것이 우선이면 무조건 정답X)



문제 풀이 후 소감

  • Lv2는 확실히 생각하는데 걸리는 시간이 Lv1보다 압도적으로 많이 걸리는 것 같다.
  • 앞으로 Lv1에 걸리는 시간이 적으면 오늘처럼 Lv2를 하나 풀어보는 것도 좋을 것 같다.
  • 조금 더 체계적으로 생각해서 생각에 걸리는 시간을 줄여보기

Table of Contents