[프로그래머스] 월간 코드 챌린지 시즌2 - 괄호 회전하기 (Java)

 

코딩테스트 연습 - 괄호 회전하기

문제 설명

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

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

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

s	s를 왼쪽으로 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 해야 합니다.

---

풀이

올바른 괄호식이 되기 위해서는

1. 여는 괄호와 닫는 괄호가 짝이 맞아야 하고(갯수 동일)

2. 여는 괄호가 닫는 괄호보다 먼저 나와야 하며(여는 괄호 갯수 >= 닫는 괄호)

3. 닫는 괄호는 여는 괄호의 역순으로 나와야 한다(후입선출) -> (예. ([{)}] 는 올바르지 않은 괄호다.)

 

여는 괄호의 갯수를 카운팅하는 방식으로 풀이할 수는 있으나, 3번의 조건까지 만족시키려면 별도의 로직이 추가된다. Stack을 이용하게 되면 더 수월하게 풀이가 가능하다.

 

문자열을 회전시키는 로직의 경우 String의 substring()을 이용하여 해결가능하다.

 

Stack의 로직을 조금 더 들여다보자.

    private boolean isRight(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char bracket = s.charAt(i);
            
            if (PRE_BRACKETS.contains(String.valueOf(bracket))) {
                stack.push(bracket);
                continue;
            }
            
            int index = POST_BRACKETS.indexOf(bracket);
            char preBracket = PRE_BRACKETS.charAt(index);
            
            if (stack.isEmpty() || stack.peek() != preBracket) {
                return false;
            }
            stack.pop();
        }
        
        return stack.isEmpty();
    }

입력받은 문자열 s를 앞에서부터 한 문자씩 순회한다.

이 때 해당 문자가 여는 괄호에 해당하면 Stack에 push()한다.

닫는 괄호에 해당하면 해당 괄호에 짝이되는 여는 괄호를 찾고, Stack의 가장 위에 올라와 있는 값과 비교한다.

 

Stack에 가장 위에 있는 괄호는 가장 먼저 닫혀야하는 괄호를 의미하고 짝이 다르다면 이는 잘못된 괄호식으로 판별한다. 이는 3번 조건을 만족하지 않는 경우다.

마찬가지로 Stack이 비어있는 경우도 닫아야할 괄호가 없는데 닫는 괄호가 먼저 나와버린 경우이므로 잘못된 괄호식이다. 이는 2번 조건을 만족하지 않는 경우다.

문자열의 순회를 마친 뒤, 올바른 문자열이라면 Stack이 비어있어야 한다. 비어있지 않는 경우는 여는 괄호가 여전히 닫히지 않고 남아 있는 것으로 1번 조건을 만족하지 않는다.

 

 

코드

import java.util.Stack;

public class Solution {

    private final String PRE_BRACKETS = "({[";
    private final String POST_BRACKETS = ")}]";

    public int solution(String s) {
        int answer = 0;

        for (int i = 0; i < s.length(); i++) {
            StringBuilder builder = new StringBuilder();
            builder.append(s.substring(i))
                         .append(s, 0, i);

            if (isRight(builder.toString())) {
                answer++;
            }
        }

        return answer;
    }
    
    private boolean isRight(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char bracket = s.charAt(i);
            
            if (PRE_BRACKETS.contains(String.valueOf(bracket))) {
                stack.push(bracket);
                continue;
            }
            
            int index = POST_BRACKETS.indexOf(bracket);
            char preBracket = PRE_BRACKETS.charAt(index);
            
            if (stack.isEmpty() || stack.peek() != preBracket) {
                return false;
            }
            stack.pop();
        }
        
        return stack.isEmpty();
    }
}