<프로그래머스> 괄호 변환(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98

[프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/60058

 

문제를 이해하는데 시간이 오래 걸렸지 코드를 작성하는 건 그렇게 오래 걸리지 않은 문제였다.

기본적으로 문제 지문이 아주 세세해서 그대로 따라만 가도 풀렸다.

물론 내가 재귀를 잘 다루지 못 했다면 그냥 벽에 부딪혔겠지만 다행히 여러번 풀어왔었기에 잘 통과했다.

이 문제도 카카오에서 낸 문제였는데 거의 30분 정도만에 풀었던 거 같다.

 

보통 지금까지 풀었던 괄호문제는 올바른 괄호인지 아닌지까지만 갔는데 이 문제는 그걸 수정해주기까지 해야했다.

아마 흐름을 문제에서 알려주지 않았다면 더 높은 레벨의 문제가 되지 않았을까 싶다.

그래서 알고리즘의 흐름은 문제를 보면 다 알 수 있다.

 

내가 이 문제를 풀면서 느낀 것들은 오랜만에 재귀함수에서 반환값을 주었었다는 것이고 확실히 문자 추가, 수정이 많은 문자열에서는 StringBuilder가 훨씬 낫다는 것이었다.

재귀함수를 쓸 때 반환값을 주면 바로 전 단계로 반환값을 보내니까 원하지 않던 방향으로 가는 경우가 많아 전역변수에다가 값을 처리하는경우가 많았는데 이번 문제는 흐름이 명확하다보니 원하는 방향으로 잘 보낼 수 있었다.

 

지나고나서 생각해보면 뭔가 어려운 부분이 없었던 거 같다.

그냥 슥슥 작성하고 디버깅하고 제출하니까 통과했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.util.Stack

class Solution {
    fun solution(p: String): String {
        return if (checkCorrect(p)) p else solve(p)
    }

    // 재귀함수
    fun solve(w: String): String {
        if (w == "") return ""
        
        // StringBuilder 사용
        val u = StringBuilder()
        val v = StringBuilder()
        var isFull = false
        val count = arrayOf(0, 0)
        w.forEach {
            if (!isFull) u.append(it)
            else v.append(it)

            if (it == '(') count[0]++
            else if (it == ')') count[1]++

            if (count[0] == count[1]) isFull = true
        }

        return if (checkCorrect(u.toString())) {
            u.toString() + solve(v.toString())
        } else {
            u.deleteCharAt(0)
            u.deleteCharAt(u.lastIndex)
            u.forEachIndexed { index, it ->
                if (it == '(') u.replace(index, index + 1, ")")
                else if (it == ')') u.replace(index, index + 1, "(")
            }

            "(" + solve(v.toString()) + ")" + u.toString()
        }
    }

    // 올바른 괄호 문자열인지 판별하는 함수
    private fun checkCorrect(s: String): Boolean {
        val stack = Stack<Char>()

        s.forEach {
            if (it == '(') {
                stack.push(it)
            }
            else {
                if (stack.isNotEmpty()) stack.pop()
            }
        }

        return stack.isEmpty()
    }
}