[알고리즘 문제/2020 KAKAO BLIND RECRUITMENT] 괄호 변환

import kotlin.test.*

class Solution {

    fun solution(s : String) : String {
        return tailrecChangeBalancedBracketToRightBracket("", s, "")
    }

    private tailrec fun tailrecChangeBalancedBracketToRightBracket(prev : String, s : String, next : String) : String {  
        return when {
            s == "" -> prev + "" + next
            s.length == 2 -> prev + "()" + next
            else -> {
                val u = getFirstBalancedMinimum(s)
        		val v = s.replaceFirst(u, "")
                
                if(checkRight(u)) {
                    tailrecChangeBalancedBracketToRightBracket(prev+u, v, next)
                } else {
                    val midle = u.subSequence(1, u.count()-1)
        			val replacedMidle = midle.toString().replace(")",",").replace("(",")").replace(",","(")
                    tailrecChangeBalancedBracketToRightBracket(prev + "(", v, ")" + replacedMidle + next)
                }
            }
        }       
    }
       
    fun checkRight(s: String) : Boolean {
        return tailrecRemovePerfectBracket(s)
    }
    
    private tailrec fun tailrecRemovePerfectBracket(s: String) : Boolean {
        if(s == "") return true
        else if(!s.contains("()")) return false
        else return tailrecRemovePerfectBracket(s.replace("()",""))
    }
    
    fun getFirstBalancedMinimum(s: String) : String {
        if(s == "") return s
        
        var prev = ""
        for(i in 0 .. s.length step 2) {
            var cur = prev + s.subSequence(i..i+1).toString()
            if(checkBalanced(cur)) return cur  
            prev = cur
        }
        return prev
    }
    
    fun checkBalanced(s: String) : Boolean {
        val openBracketCount = s.filter({char -> char == '('}).count()
        val closeBracketCount = s.filter({char -> char == ')'}).count()
        return openBracketCount == closeBracketCount
    }
}

class SolutionTest(private val solution : Solution) {

    fun testCheckBalanced() {

        val testCase1 = Pair("(()())", true)
        val testCase2 = Pair("((", false)
        val testCase3 = Pair(")", false)
        val testCase4 = Pair(")(", true)
        val testCase5 = Pair("()()", true)
        val testCase6 = Pair("", true)

		val testCases = listOf(testCase1 , testCase2, testCase3, testCase4, testCase5, testCase6)

		for (test in testCases) {
            val (quest, answer) = test
            val result = solution.checkBalanced(quest)
            assertEquals(answer, result, "epected : $answer, actural : $result")
        }
    }
    
    fun testGetFirstBalancedMinimum() {
        val testCase1 = Pair("(()())", "(()())")
        val testCase2 = Pair("(())()", "(())")
        val testCase3 = Pair(")))))(())(((()((", ")))))(())(((()((")
        val testCase4 = Pair(")(", ")(")
        val testCase5 = Pair("()()", "()")
        val testCase6 = Pair("", "")

		val testCases = listOf(testCase1 , testCase2, testCase3, testCase4, testCase5, testCase6)

        testCases.forEachIndexed{ i, test ->
            val (quest, answer) = test
            val result = solution.getFirstBalancedMinimum(quest)
            assertEquals(answer, result, "epected : $answer, actural : $result") 
        }
    }
    
    fun testCheckRight() {
        val testCase1 = Pair("(()())", true)
        val testCase2 = Pair("(())", true)
        val testCase3 = Pair(")))))(())(((()((", false)
        val testCase4 = Pair(")(", false)
        val testCase5 = Pair("()", true)
        val testCase6 = Pair("", true)

		val testCases = listOf(testCase1 , testCase2, testCase3, testCase4, testCase5, testCase6)

        testCases.forEachIndexed{ i, test ->
            val (quest, answer) = test
            val result = solution.checkRight(quest)
            assertEquals(answer, result, "epected : $answer, actural : $result") 
        }
    }
    
    fun testSolution() {

        val testCase1 = Pair("(()())()", "(()())()")
        val testCase2 = Pair(")(","()")
        val testCase3 = Pair("()))((()","()(())()")
        val testCase4 = Pair(")()()()(", "(((())))")

        val testCases = listOf(testCase1 , testCase2, testCase3, testCase4)

        for(test in testCases) {
            val (string, answer) = test
            val result = solution.solution(string)
            assertEquals(answer, result, "epected : $answer, actural : $result")
        } 
    }

}

fun main() {    
    
    val solution = Solution()
    val solutionTest = SolutionTest(solution) 

	solutionTest.testCheckBalanced()
    solutionTest.testGetFirstBalancedMinimum()
    solutionTest.testCheckRight()
    solutionTest.testSolution()

}