TIL 21일차 (괄호 회전하기 - Kotlin)

코드카타

 

괄호 회전하기

 

문제

 

올바른 괄호 문자열은 여는 괄호 앞에 닫는 괄호가 위치하면 안되고,

여는 괄호가 문자열에 존재한다면 그 괄호의 모양과 일치하는 닫는 괄호도 존재해야 한다.

 

 

입출력 예시

 

주어진 괄호 문자열을 순회하며 회전을 진행한 괄호 문자열이

올바른 괄호 문자열인지 판별하는 로직이 필요하다. 

 

 

풀이

class Solution {
    // 괄호의 짝이 맞는지 검사하기 위해 괄호 맵 선언
    val bracketMap = mapOf('(' to ')', '[' to ']', '{' to '}')
    
    // 괄호 문자열(Bracket String)이 올바른 형태인지 검사하는 함수
    fun isBsValid(rs: String): Boolean {
        val stack = mutableListOf<Char>()
        for (i in rs) {
            if (i in bracketMap.keys) stack.add(i)
            else {
                if (stack.isNotEmpty() && i == bracketMap[stack.last()]) {
                    stack.removeLast()
                } else return false
            }
        }
        return stack.isEmpty()
    }
    
    // x만큼 왼쪽으로 회전을 진행한 괄호 문자열을 반환하는 함수
    fun rotateStr(s: String, x: Int): String {
        return s.substring(x) + s.substring(0, x)
    }

    fun solution(s: String): Int {
        var cnt = 0 // 올바른 괄호 문자열이 되는 경우의 수
        
        // 주어진 괄호 문자열을 순회하며
        for (i in s.indices) {
            // 회전을 진행한 괄호 문자열이 올바른 괄호 문자열인지 검사
            if (isBsValid(rotateStr(s, i))) cnt++
        }
        return cnt
    }
}

주어진 괄호 문자열이 올바른 형태인지 검사하는 함수와

x만큼 왼쪽으로 회전시킨 괄호 문자열을 반환하는 함수를 작성한다.

 

solution함수에서 주어진 괄호 문자열을 순회하며

올바른 괄호 문자열이 되는 경우의 수를 반환한다. 

 

 

괄호 맵 선언

val bracketMap = mapOf('(' to ')', '[' to ']', '{' to '}')

주어진 괄호 문자열이 올바른 형식인지 검사하기 위해 선언한 맵이다.

 

맵의 요소 즉 key와 value는 전부 문자(Char)에 해당한다. 

맵의 key는 여는 괄호에 해당하고, 맵의 value은 닫는 괄호에 해당한다.

 

해당 맵을 이용해 모양이 맞는 괄호끼리 매치가 되는지 확인할 수 있다.

 

 

괄호 문자열이 올바른 형태인지 검사

fun isBsValid(rs: String): Boolean {
    // 여는 괄호를 관리하는데 사용되는 스택
    val stack = mutableListOf<Char>()
    
    // 주어진 문자열을 순회
    for (i in rs) {
    	// i가 여는 괄호에 해당한다면 스택에 i를 추가
        if (i in bracketMap.keys) stack.add(i)
        // i가 닫는 괄호에 해당한다면
        else {
            // 스택이 비어있지 않고 괄호 모양이 일치한다면
            if (stack.isNotEmpty() && i == bracketMap[stack.last()]) {
                stack.removeLast() // 스택에서 해당 괄호를 제거하고
            } else return false // 아니라면 false를 반환
        }
    }
    return stack.isEmpty() // 스택이 비어있다면 true 반환
}

인자 값으로 주어진 괄호 문자열 rs(Rotate String)가

올바른 형태에 해당하는지 검사하고 그 결과에 따라 Boolean값을 반환하는 함수이다.

 

i가 닫는 괄호에 해당할 때, 스택이 비어있는지 검사함으로써 

괄호 문자열이 닫는 괄호로 시작한다면 해당함수는 false를 반환하게 된다.

 

bracketMap은 같은 모양의 괄호끼리 짝 지어 놓은 맵이며

만약 i가 닫는 괄호에 해당한다면 stack.last()는 최근에 추가된 닫는 괄호에 해당한다.

 

조건문 i == bracketMap[stack.last()]는 i(닫는 괄호)의 모양이

스택에 있는 여는 괄호와 일치하지 않는다면 false를 반환하게 된다.

 

주어진 괄호 문자열이 올바른 형태라면, 즉 모든 괄호가 알맞게 짝 지어진다면

스택에는 아무런 요소도 남지 않게 되기에 해당 함수는 true를 반환한다.

 

 

회전 문자열 반환 함수

 fun rotateStr(s: String, x: Int): String {
	return s.substring(x) + s.substring(0, x)
}

s를 왼쪽으로 x만큼 회전한 문자열을 반환하는 함수이다.

 

 

fun main() {
    var s = "[](){}"
    
    println(s.substring(1)) // ](){}
    println(s.substring(0, 1)) // [
}

substring 함수를 이용해 문자열을 원하는 만큼 자를 수 있다.

 

substring(n)은 n번지부터 끝까지에 해당하는 부분 문자열을 반환하고,

substring(0, n)은 처음부터 n - 1번지까지 자른 부분 문자열을 반환한다.

 

 

solution 함수 로직

for (i in s.indices) {
    if (isBsValid(rotateStr(s, i))) cnt++
}

주어진 문자열을 순회하면서 올바른 괄호 문자열이 되는 모든 경우의 수를 세는 로직이다.

 

roateStr의 x값은 s의 인덱스로 들어가게 되는데

이 때 i가 0인 경우 즉, rotateStr(s, 0)은 s를 반환하게 된다.

 

, 왜냐하면 substring 함수는 시작 인덱스와 종료 인덱스가 동일할 때 빈 문자열을 반환하기에

s.substring(0) + s.substring(0, 0) => 괄호 문자열 + 빈 문자열 => 최종적으로 s를 반환한다.

 

 

회고

저번 주에 연산자 우선순위를 고려해 연산식의 결과를 반환하는 로직을 구현하기 위해

중위 표기법으로 표기된 연산식을 후위 표기법으로 변환하는 함수를 짰었는데

 

그 때문에 괄호 문자열이 올바른 형태인지 검사하는 함수의 로직을

비교적 쉽게 이해할 수 있었던 것 같다.

 

subString으로 정해진 부분의 문자열을 자를 수 있다는 것은 알았지만

인자값의 개수에 따라 반환 값(부분 문자열)이 달라지는 것은 처음 알았다.

 

특수 기호가 포함된 문자열을 다루는 문제는

맵 자료형과 스택의 개념을 이용해 풀 수 있다는 사실을 알게 되었다.