Lesson7 - Brackets

자세한 문제는 여기서 확인하시면 됩니다.

 

간략하게 설명하면 String이 "{[()()]}"이렇게 짝이 맞으면 1, 짝이 맞지 않다면 0을 반환하도록 합니다. 비어 있을 경우에도 1을 반환합니다. 들어갈수 있는 문자는 "{" "[" "(" ")" "]" "}" 입니다.

 

우선 문제의 힌트는 Lesson7이 stack과 queue에 관련된 문제라는 것에서 둘중 하나를 사용하면 된다는 것을 유추할 수 있습니다. 

 

그렇게 생각한 풀이 알고리즘은

1.String이 비어있으면 1을 반환

2.String의 길이가 짝수가 아닐 경우 0을 반환 (짝수가 아니라면 괄호의 짝이 맞지 않기 때문입니다.)

3.String을 처음부터 확인하면 "{" "[" "("들 하나라면 stack에 쌓고  ")" "]" "}"라면 스텍에서 문자를 꺼네서 짝을 확인하고, 짝이 맞지 않으면 0을 반환 합니다.

4.String의 짝을 다 확인하고 stack에 문자가 남아있다면 0을 반환하도록 합니다.(짝을 다 확인했는데도 문자가 남아있다면 짝수로 { [ ( 이 문자들이 남아있다는 의미기 떄문입니다.)

 

위의 알고리즘에 맞는 code를 만들어 보면

fun solution(S: String): Int {
       if(S.isEmpty()) return 1
    if(S.length%2 != 0)  return 0

    val stack = mutableListOf<String>()
    for(i in S.indices ){
        val c_string = S[i].toString()
        if(c_string == "{" || c_string == "[" ||c_string== "("){
            stack.push(c_string)
        }else {
            if(stack.isEmpty()) return 0
            val s_pop = stack.pop()
            if(s_pop == "{"){
                if(c_string != "}")  return 0
            }else if(s_pop == "["){
                if(c_string != "]") return 0
            }else if(s_pop =="("){
                if(c_string != ")")  return 0
            }
        }
    }
    if(!stack.isEmpty()) return 0
    return 1
}
fun MutableList<String>.push(str:String){
    this.add(str)
}
fun MutableList<String>.pop() : String{
    val result = this.last()
    this.removeAt(this.size-1)
    return result
}

이렇게 됩니다.

 

사실 java.util에 stack을 제공하지만 codility에서는 java.util에 있는 stack을 쓸수 없기 때문에 직접 stack을 만들서 사용하였습니다.