2024.06.16 TIL 코트카타 84번 (괄호 회전하기)

    fun solution(s: String): Int {
        var numCorrectRotate = 0
        var numRotate = 0
        val sToBuilder = StringBuilder(s)

        if(isCorrectBrakets(sToBuilder))
            numCorrectRotate++

        while (numRotate < s.length - 1) {
            sToBuilder.append(sToBuilder[0])
            sToBuilder.deleteCharAt(0)

            if(isCorrectBrakets(sToBuilder))
                numCorrectRotate++

            numRotate++
        }

        return numCorrectRotate
    }

    fun isCorrectBrakets(brackets: StringBuilder): Boolean{
        val bracketStack = Stack<Char>()
        val closeBrackets = mutableListOf(')','}',']')
        val closeToOpen = mutableMapOf(')' to '(', '}' to '{', ']' to '[')

        for (bracket in brackets) {
            if (bracket in closeBrackets) {
                if (bracketStack.isNotEmpty() && closeToOpen[bracket] == bracketStack.peek())
                    bracketStack.pop()
                else
                    return false
            } else
                bracketStack.push(bracket)
        }

        return bracketStack.isEmpty()
    }

 

풀이 과정

1. s의 괄호를 순서대로 스택에 push한다.

2. 닫는 괄호가 나왔을 때

   2.1. 스택이 비어있지 않고 이전 push한(peek한) 괄호가 쌍을 이루는 여는 괄호일 경우 pop한다.

   2.2. 아닐경우 잘못된 괄호 셋

3. s 전체를 돌았을 때 stack이 비어있으면 올바른 괄호 셋으로 count한다.

4. 왼쪽으로 한 칸씩 이동하며 2~3번의 과정을 반복한다.

 

포인트

- stack에서 닫는 괄호가 나왔을 때 쌍을 이루는 여는 괄호가 stack의 가장 위에 있어야 올바른 괄호 셋이 된다는 것을 활용한다.

- 중첩되는 괄호더라도 올바른 괄호 셋이라면 가장 안쪽 괄호부터 쌍에 맞춰져 stack에 push되었기 때문이다.