중괄호 짝 맞추기 문제 풀이

 

주어진 문자열에서 중괄호 {와 }가 올바르게 짝을 이루고 있는지 판별하는 함수를 작성하세요. 올바른 짝을 이루고 있다면 true, 그렇지 않다면 false를 반환해야 합니다.

해결 전략

이 문제를 해결하기 위해선 스택이라는 자료구조를 활용합니다. 스택은 LIFO(Last In, First Out)의 특징을 가진 자료구조로, 마지막에 들어간 요소가 가장 먼저 나오게 됩니다.

fun isValidBrackets(s: String): Boolean {
    val stack = mutableListOf<Char>()
    for (ch in s) {
        when (ch) {
            '{' -> stack.add(ch)
            '}' -> {
                if (stack.isNotEmpty() && stack.last() == '{') {
                    stack.removeAt(stack.size - 1)
                } else {
                    return false
                }
            }
            else -> return false  // 문제 조건 외 문자가 포함된 경우
        }
    }
    return stack.isEmpty()
}

코드 설명

• 스택을 사용하여 {를 만나면 스택에 삽입합니다.
• }를 만나면 스택에서 마지막 요소를 확인하고, 마지막 요소가 {라면 스택에서 제거합니다. 만약 {가 아니라면 false를 반환합니다.
• 문자열 순회가 끝났을 때 스택이 비어있다면 모든 중괄호가 올바르게 짝을 이루고 있는 것이므로 true를 반환하고, 그렇지 않다면 false를 반환합니다.

fun main() {
    testIsValidBrackets()
}

fun testIsValidBrackets() {
    println(isValidBrackets("{}{}{}") == true)
    println(isValidBrackets("{{{{}}}}") == true)
    println(isValidBrackets("{") == false)
    println(isValidBrackets("}") == false)
    println(isValidBrackets("{}{") == false)
    println(isValidBrackets("}{") == false)
    println(isValidBrackets("{{{}}") == false)
    println(isValidBrackets("{}{}{{}") == false)
    println(isValidBrackets("abc") == false)
}