괄호 회전하기(Lv.2)

프로그래머스

문제 설명

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

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 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

• 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바르냐?
0	"[](){}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}[]()"	O
5	"}[](){"	X

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

• 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

x	회전	올바름?
0	"}]()[{"	X
1	"]()[{}"	X
2	"()[{}]"	O
3	")[{}]("	X
4	"[{}]()"	O
5	"{}]()["	X

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

---

풀이

풀이를 위해 짜야할 알고리즘은 2가지 입니다. 

• 문자열 s를 왼쪽으로 한 칸씩 회전
• 올바른 괄호 문자열인지 정의

일단 문제에서 x값을 주지 않았기 때문에 x = 1로 가정하고 풀었습니다.

1. 문자열 s를 회전

import java.util.*

class Solution {
    fun solution(s: String): Int {
        if(s.length % 2 != 0)
            return 0

        var answer = 0
        val sb = StringBuilder(s)

        while(true){
        	...
            //왼쪽으로 이동
            sb.append(sb[0])
            sb.deleteCharAt(0)
            //원래와 같아지면 종료
            if(s == sb.toString())
                break
            ...
        }
        return answer
    }
}

StringBuilder를 이용해 풀었습니다. 맨 마지막에 첫 문자열을 append시키고 첫 문자열을 삭제한 뒤 패러미터 s와 같으면 종료하도록 했습니다. while문에 조건을 넣게되면 이동을 한 번 시킨 뒤에 반복시켜야 하므로 true로 줬습니다. 주어진 문자열의 길이가 홀수라면 짝이되는 괄호가 100% 없으므로 조건문으로 배재시켰습니다.

2. 중괄호 검사

//짝이되는 괄호 문자열 검사
sb.forEach {
    when{
        stack.isEmpty() -> stack.add(it)
        (it == ')' && stack.peek() == '(') || (it == '}' && stack.peek() == '{') || (it == ']' && stack.peek() == '[') -> stack.pop()
        else -> stack.add(it)
    }
}
...
//스택이 비어있으면 +1
if(stack.isEmpty())
    answer++
stack.clear()

스택을 이용해서 풀었습니다.

• 스택이 비었을 경우? => add
• 입력받은 문자가 닫는 괄호이면서 스택의 최상위 원소와 짝을 이룰경우 => pop
• 그 외( 입력받은 문자가 닫는 괄호이지만 짝이 안맞을 경우 => add

로 조건을 잡고 when 조건문으로 짰습니다.

괄호 검사를 마친 뒤 스택이 비어있으면 결과값에 1을 더해줬습니다.

이후 스택을 초기화시켜서 반복합니다.

전체코드

import java.util.*

class Solution {
    fun solution(s: String): Int {
        if(s.length % 2 != 0)
            return 0

        var answer = 0
        val sb = StringBuilder(s)
        var stack = Stack<Char>()

        while(true){
            //짝이되는 괄호 문자열 검사
            sb.forEach {
                when{
                    stack.isEmpty() -> stack.add(it)
                    (it == ')' && stack.peek() == '(') || (it == '}' && stack.peek() == '{') || (it == ']' && stack.peek() == '[') -> stack.pop()
                    else -> stack.add(it)
                }
            }
            //왼쪽으로 이동
            sb.append(sb[0])
            sb.deleteCharAt(0)
            //원래와 같아지면 종료
            if(s == sb.toString())
                break
            //스택이 비어있으면 +1
            if(stack.isEmpty())
                answer++
            stack.clear()
        }
        return answer
    }
}

전체코드입니다.