04/03 알고리즘 공부(84) - 괄호 회전하기

조건

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한조건

• s의 길이는 1 이상 1,000 이하입니다.

입출력 예

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

알고리즘 예상

1. 입력받은 문자열 s를 mutableList<Char>형태로 바꾼다.
2. for(i in s.indice) 내부에 for(j in sList)를 작성한다.
3. i를 이용한 반복문에 isCorrect = false를 선언한다.
4. Stack을 이용해서 앞에서부터 하나씩 push하되 닫는 괄호가 나오면 2개를 pop해 순서가 맞는지 확인한다.
5. 순서가 맞지 않으면 isCorrect = false, break, 끝까지 순서가 맞으면 isCorrect = true를 설정한다.
6. isCorrect가 true면 answer ++, false면 아무것도 하지 않는다.
7. s.add(s[0]), s.removeAt(0)를 한다.

 

초기 코드

class Solution {
    fun solution(s: String): Int {
        var answer: Int = -1
        return answer
    }
}

 

내 코드

//예외 발생
import java.util.Stack

class Solution {
    fun solution(s: String): Int {
        var answer: Int = 0
        val sList = s.toMutableList()

        for (i in s.indices) {
            var isCorrect = false
            val sStack = Stack<Char>()
            for (j in sList) {
                sStack.push(j)
                when (j) {
                    ']' -> {
                        sStack.pop()
                        if (sStack.pop() != '[') {
                            isCorrect = false
                            break
                        }
                    }

                    '}' -> {
                        sStack.pop()
                        if (sStack.pop() != '{') {
                            isCorrect = false
                            break
                        }
                    }

                    ')' -> {
                        sStack.pop()
                        if (sStack.pop() != '(') {
                            isCorrect = false
                            break
                        }
                    }
                }
                isCorrect = true
            }
            if (isCorrect) answer++

            sList.add(sList[0])
            sList.removeAt(0)

        }


        return answer
    }
}

첫 문자가 닫는 괄호일 때 stack에 두번 pop할 요소가 없어서 예외가 발생했다. 우선은 공백을 추가해주기로 했다.

//테스트 케이스 통과 채점 실패
import java.util.Stack

class Solution {
    fun solution(s: String): Int {
        var answer: Int = 0
        val sList = s.toMutableList()

        for (i in s.indices) {
            var isCorrect = false
            val sStack = Stack<Char>()
            sStack.push(' ')
            for (j in sList) {
                sStack.push(j)
                when (j) {
                    ']' -> {
                        sStack.pop()
                        if (sStack.pop() != '[') {
                            isCorrect = false
                            break
                        }
                    }

                    '}' -> {
                        sStack.pop()
                        if (sStack.pop() != '{') {
                            isCorrect = false
                            break
                        }
                    }

                    ')' -> {
                        sStack.pop()
                        if (sStack.pop() != '(') {
                            isCorrect = false
                            break
                        }
                    }
                }
                isCorrect = true
            }
            if (isCorrect) answer++

            sList.add(sList[0])
            sList.removeAt(0)

        }
        return answer
    }
}

13번케이스에서 실패가 발생했다. 짝이 맞지 않는 경우, 즉 "[]("와 같은 문자열에 대해 실패가 발생하는 것 같다.isCorrect를 길이가 1(처음 추가한 공백)이면 true로 반환하게 바꾸기로 했다.

import java.util.Stack

class Solution {
    fun solution(s: String): Int {
        var answer: Int = 0
        val sList = s.toMutableList()

        for (i in s.indices) {
            var isCorrect = false
            val sStack = Stack<Char>()
            sStack.push('a')
            for (j in sList) {
                sStack.push(j)
                when (j) {
                    ']' -> {
                        sStack.pop()
                        if (sStack.pop() != '[') {
                            isCorrect = false
                            break
                        }
                    }

                    '}' -> {
                        sStack.pop()
                        if (sStack.pop() != '{') {
                            isCorrect = false
                            break
                        }
                    }

                    ')' -> {
                        sStack.pop()
                        if (sStack.pop() != '(') {
                            isCorrect = false
                            break
                        }
                    }
                }
                if(sStack.size == 1) isCorrect = true
                else isCorrect = false
            }
            if (isCorrect) answer++

            sList.add(sList[0])
            sList.removeAt(0)

        }
        return answer
    }
}

통과했다. 연산과정을 조금 줄이려면 push를 when문의 else 안에 넣고 pop을 1번만 할 수 있을 것이다.

다른 사람의 풀이

class Solution {
    fun solution(s: String): Int {
        var answer: Int = 0

        for(i in 0..s.length-1) {
            var tmp = s.substring(i)+s.substring(0,i)
            if(isRight(tmp)) {
                answer+=1
            }
        }
        return answer
    }

    fun isRight(str: String): Boolean {
        var list = mutableListOf<Char>()
        var endCh = charArrayOf(']',')','}')

        for(ch in str) {
            if(endCh.contains(ch)) {
                if(list.isEmpty()) {
                    return false
                }
                var tmp=list.removeAt(list.size-1)
                when(ch) {
                    ']' -> if(tmp!='[') return false
                    ')' -> if(tmp!='(') return false
                    '}' -> if(tmp!='{') return false
                }
            } else {
                list.add(ch)
            }
        }
        return list.size==0
    }
}

 

개선점 또는 배운점

1. stack이 아니라 List와 substring을 이용해 비슷하게 푼 풀이이다. endCh라는 배열을 통해 처음에 온 괄호가 닫는괄호면 false를 반환하게 했다.

 

개선된 코드

import java.util.Stack

class Solution {
    fun solution(s: String): Int {
        var answer: Int = 0
        val sList = s.toMutableList()

        for (i in s.indices) {
            var isCorrect = false
            val sStack = Stack<Char>()
            sStack.push('a')
            for (j in sList) {
                when (j) {
                    ']' -> {
                        if (sStack.pop() != '[') {
                            isCorrect = false
                            break
                        }
                    }

                    '}' -> {
                        if (sStack.pop() != '{') {
                            isCorrect = false
                            break
                        }
                    }

                    ')' -> {
                        if (sStack.pop() != '(') {
                            isCorrect = false
                            break
                        }
                    }
                    else -> sStack.push(j)
                }
                if(sStack.size == 1) isCorrect = true
                else isCorrect = false
            }
            if (isCorrect) answer++

            sList.add(sList[0])
            sList.removeAt(0)

        }
        return answer
    }
}