[Kotlin] 99 클럽 코딩 테스트 스터디 미들러 28일차 - 괄호 회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/76502?language=kotlin

프로그래머스

[문제]

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {}는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, []가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

[입출력 예]

 

[풀이]

openBracket, closeBracket을 구분하여 아래와 같이 배열을 선언해 줍니다.

res는 결과 값을 담을 변수로서 문제에 따라 초기값은 0입니다.

val openBracket = charArrayOf('(', '{', '[')
val closeBracket = charArrayOf(')', '}', ']')
var res = 0

 

주어진 s의 각 char를 Queue로 정리하고, 원형 큐로 생각하여 문자열 길이만큼 맨 뒤 요소를 앞으로 끌어와서 회전하는 식으로 반복문을 구성해 줍니다. 그리고 매번 변경된 Queue를 String으로 묶어 스택을 통해 Bracket 유효성 처리를 진행해주어야 합니다.

val queue: Queue<Char> = LinkedList()
s.forEach { queue.add(it) }

...

repeat(s.length) {
    if (isSuccess(queue.joinToString(""))) res ++
    val last = queue.remove()
    queue.offer(last)
}

isSuccess라는 함수 내부에서 스택을 활용한 검사를 진행합니다.

연산이 끝난 이후에는 큐의 마지막 요소를 꺼내서 맨 앞으로 offer 해줍니다.

 

isSuccess 함수는 해당 문자열이 Bracket 구성이 유효한지 Bool 값으로 반환해 줍니다.

fun isSuccess(s: String): Boolean {
    val stack = Stack<Char>()
    var flag: Boolean
    for (c in closeBracket) if (c == s[0]) return false

    for (c in s) {
        flag = false
        for (i in openBracket.indices) {
            if (stack.isNotEmpty() 
    			&& stack.peek() == openBracket[i] 
        		&& c == closeBracket[i]) flag = true
        }
        if (flag) stack.pop() else stack.add(c)
    }
    return stack.isEmpty()
}

 

규칙에 따라 close Bracket이 문자열 첫 번째로 오면 실패로 간주합니다.

플래그 변수를 하나 선언하여, 만일 Stack의 최상위와 지금 비교 대상인 char가 Open - Close Bracket 관계라면 true로 간주하고 스택에 있는 최상위 값을 pop 합니다. 정상적인 Bracket 관계가 아니라면 스택에 추가하고 다음 반복문 차례에서 검사합니다.

이렇게 진행했을 때에 최종적으로 모든 Char가 순차적으로 Bracket 관계가 맞다면 스택이 빌 것이고, 관계 형성이 불가능하다면 스택이 비어있지 못할 것입니다.

이에 따라 참인 경우를 res 변수에 카운트하여 답을 구할 수 있습니다.

 

전체 코틀린 코드입니다.

import java.util.*
import java.util.LinkedList

class Solution {
    fun solution(s: String): Int {
        val openBracket = charArrayOf('(', '{', '[')
        val closeBracket = charArrayOf(')', '}', ']')
        var res = 0

        val queue: Queue<Char> = LinkedList()
        s.forEach { queue.add(it) }

        fun isSuccess(s: String): Boolean {
            val stack = Stack<Char>()
            var flag: Boolean
            for (c in closeBracket) if (c == s[0]) return false

            for (c in s) {
                flag = false
                for (i in openBracket.indices) {
                    if (stack.isNotEmpty() && stack.peek() == openBracket[i] && c == closeBracket[i]) flag = true
                }
                if (flag) stack.pop() else stack.add(c)
            }
            return stack.isEmpty()
        }

        repeat(s.length) {
            if (isSuccess(queue.joinToString(""))) res ++
            val last = queue.remove()
            queue.offer(last)
        }
        return res
    }
}