프로그래머스 Level 2 괄호 회전하기

문제 : 괄호 회전하기 

출처: 프로그래머스

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

프로그래머스

이 포스트는 광고 노출이 없는 비영리, 비상업적 포스트입니다.

 

풀이

첫 번째 

class Solution8 {
    fun solution(s: String): Int {
        var answer: Int = 0
        var str = s
        while (true) {
            val stack = Stack<Char>()
            for (i in str.indices) {
                val item = str[i]
                stack.add(item)
                if (stack.size > 1) {
                    if (stack[stack.lastIndex - 1] == '(' && stack.peek() == ')') {
                        stack.pop()
                        stack.pop()
                    } else if (stack[stack.lastIndex - 1] == '{' && stack.peek() == '}') {
                        stack.pop()
                        stack.pop()
                    } else if (stack[stack.lastIndex - 1] == '[' && stack.peek() == ']') {
                        stack.pop()
                        stack.pop()
                    }
                }
            }
            str = str.substring(1 until str.length) + str.first()
            if (stack.isEmpty()) answer++
            if (str == s) break
        }
        return answer
    }
}

 

두 번째

class Solution8 {
    fun solution(s: String): Int {
        var answer: Int = 0
        val str = mutableListOf<Char>()
        val stack = mutableListOf<Char>()
        s.forEach { str.add(it) }
        repeat(s.length) {
            var i = 0
            while (i <= str.size - 1) {
                if ((str[i] == ')' || str[i] == '}' || str[i] == ']')) {
                    if (stack.isEmpty()) break
                    else {
                        when (str[i]) {
                            ')' -> { if (stack.last() == '(') stack.removeLast() else break }
                            '}' -> { if (stack.last() == '{') stack.removeLast() else break }
                            else -> { if (stack.last() == '[') stack.removeLast() else break }
                        }
                    }
                }
                else { stack.add(str[i]) }
                i++
            }
            if (i==str.size && stack.isEmpty()) { answer++ }
            str.add(str.removeFirst())
        }
        return answer
    }
}

 

결과 비교

왼쪽 첫 번째 풀이 - 오른쪽 두 번째 풀이

설명

첫 번째의 과정은 간단하게 요약해서

1. str 앞을 잘라서 뒤에 붙이는 과정을 반복한다.

2. 현재 str을 stack을 이용해 검사한다.

3. 스택에 str [i]를 넣고 스택 끝에 2개의 원소가 하나의 괄호 묶음이면 pop 2번 한다.

4. 비어있으면 answer++ 그리고 str을 잘라서 붙이는 과정이 돌아서 다시 자기 자신이 되었으면 while 종료

 

두 번째의 과정은 간단하게 요약해서

1. 총길이만큼 str list에서 맨 앞 원소를 빼 뒤에 더하는 과정을 반복한다.

2. while문으로 str [i]를 확인하는데 str [i]가 여는 괄호이면 더하고 아니면 검사한다.

3. 닫는 괄호인데 현재 검사 stack이 비어있으면 불가능하므로 break

4. 닫는 괄호인데 stack이 비어있지 않고 stack의 마지막 원소가 닫는 괄호와 같다면 stack 마지막 삭제

5. 여는 괄호랑 닫는 괄호가 다르면 불가능하므로 break

6. i가 끝까지 갔고 stack이 비어있지 않으면 answer 증가

 

왜 두 번째가 더 짧은 시간이 걸리나

1. 문자열 앞에를 뒤에 붙일 때 subString 하는 과정이 없다.

2. add 연산을 무조건 하지 않는다

3. 괄호가 세트일때 pop을 한 번만 한다.

4. 가능하지 않은 경우는 탈출하므로 반복문을 끝까지 돌지 않는다.

 

문제의 중요 포인트는 스택 원리의 활용이라고 생각합니다. 또한 시간을 더 짧게 할 수도 있겠지만 그냥 여기까지만 하겠습니다 이상 마치겠습니다. 감사합니다.