괄호 회전하기(2레벨)

 

import java.util.*
class Solution {
    fun solution(s: String): Int {
        var answer: Int = 0
        var moveStr = ""
        var remainStr = s
        var stack = Stack<Char>()
        for(i in 0..s.length-1)
        {
            moveStr = remainStr[0].toString()
            for(i in 0..remainStr.length-1)
            {
                if(remainStr[i] == '(' || remainStr[i] == '[' || remainStr[i] == '{')
                {
                    stack.push(remainStr[i])
                }
                else
                {
                    if(stack.size!=0)
                    {
                        when(stack.peek())
                        {
                        '(' ->
                            {
                            if(remainStr[i] == ')')
                                stack.pop()
                            }
                        
                        '{' ->
                            {
                            if(remainStr[i] == '}')
                                stack.pop()
                            }
                        
                        '[' ->
                            {
                            if(remainStr[i] == ']')
                                stack.pop()
                            }
                        }
                        
                    }
                    else
                    {
                        stack.push(remainStr[i])
                    }
                }
                    
            }

            if(stack.size==0) answer++
            
            while(stack.size!=0)
            {
                stack.pop()
            }
            
            remainStr= remainStr.substring(1,s.length)
            remainStr+= moveStr
  			//한칸씩 이동
        }
        return answer
    }
}

너무 어렵게 생각한 것 같다.

예전에 스택을 활용해 괄호가 있는 계산기 만드는 알고리즘을 배웠다.

그 때 새로운 괄호가 열릴때마다 스택을 동적으로 생성해서 해결하길래 그런식으로 접근해보았다.

 

결론적으로는 스택을 활용하는건 맞았지만 올바른 괄호의 구조가 스택의 구조와 동일해야 한다는 게 

이 문제의 핵심 인 것 같다.

 

해설

주어진 s에서 하나씩 가져와서 괄호가 열리면 스택에 넣고
닫히는 괄호라면 스택이 비어있는지 체크 한후
비어있으면 스택에 넣고
비어있지않으면
스택에서 꺼내 짝이 맞는지 확인한다.
짝이 맞으면 스택에서 제거하는 식으로 반복한다.
결론적으로 새로운 괄호를 열려면 기존 괄호가 닫혀서는 안되기 떄문에 이 방식을 사용하면
올바른 괄호의 문장은 스택에 아무것도 남아 있지 않게된다.
이를 문장을 한칸씩 왼쪽으로 밀어가며 반복해주고 올바른 문장일시 answer를 증가시켜주면 된다.