[CodeGround] 괄호 문제

이번에는 코드그라운드의 괄호문제 입니다. codeground

문제를 간단하게 말하면 괄호 순서가 올바르게 된 부분 문자열의 최대 길이를 구하라는 겁니다!!

괄호 문제는 사실 유명하죠!! 여러 곳에서 나오는 문제 중 하나입니다. 이 문제는 괄호의 성질을 잘 생각해보면 간단하게 풀 수 있는데, 한번 봅시다.

[{}()] 이런 경우는 올바른 괄호가 되겠죠. 모두 잘 닫혔으니까.

[]{)[] 이런 경우는 가운데 {)이거 때문에 제대로 되지 않겠네요.

괄호는 한번 열리면 같은 모양으로 반드시 닫혀야 하는 성질이 있죠. 이를 잘 생각해보면 가장 최근에 열린 괄호는 먼저 닫혀야 한다.라는 결론이 나오네요!!

조금 느낌이 오시나요?? 정답은 stack에 있습니다!! stack으로 풀면 해결은 되는데 코드그라운드에서는 time overㅠㅠ

그래도 풀이를 한번 봅시다..ㅎㅎ 제 풀이는 이러합니다!

---

• [ { ( 를 만나면 stack에 push를 한다.
• ) } ] 를 만났는데 stack이 비어 있으면 부분 문자열 길이를 저장한 값이랑 비교해보고 초기화 한다.
• 위의 경우에서 stack의 pop한 값이 올바른 괄호인 (), {}, []를 이루면 부분 문자열 길이에 2를 더한다.

---

for(int i=0; i<strlen(string); i++)
{
    if((string[i]=='(')||(string[i]=='{')||(string[i]=='['))
    {
         if(matchCheck(string[i+1],string[i]))
         {
             maximum+=2; i+=1;
             continue;
         }
         else stack.push(string[i]);
    }
    else if(stack.empty()) // ({[이 아닌데 스택이 비었어
    {
         Answer = (Answer>=maximum) ? Answer : maximum;
         maximum = 0;
         continue;
     }
     if(matchCheck(string[i],stack.top())) // 스택이 안비었고 )}]이야 그리고 match해
     {
          maximum+=2;
          stack.pop();
     }
}

코드로 간단하게 해봤습니다! 시간을 최대한 줄이고자 바로 붙어있는 관계를 바로 탐색하게 했는데 그래도 시간 초과가 뜨네요..ㅠㅠ

 

전체 코드는 여깁니다!! Code