🔥[99클럽 코테 스터디] 28일차 TIL - 괄호 회전하기

⏳문제

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

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 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	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. 문자열을 어떻게 회전시킬까

우선, 문자열 s를 회전시키는 방법에 대해 생각해 보았다.

s가 만약 "()[]{}"라면, 고려해야 할 문자열들은 아래와 같다.

• "()[]{}"
• ")[]{}("
• "[]{}()"
• "]{}()["
• "{}()[]"
• "}()[]{"

이렇게 총 6가지의 String을 반복적인 규칙을 통해 구해야 하는데,
이 때 substring() 메서드를 통해 구현할 수 있었다.
substring() 메서드는 String 문자열을 일정 구간 슬라이싱 해주는 역할을 하는데,
기존의 문자열 s에서 인덱스를 잘 활용하면 위와 같이 문자열을 회전시키는 것처럼 구현할 수 있다.

String str = s.substring(i, s.length()) + s.substring(0, i);

이런 식으로 코드를 작성하면, 왼쪽으로 i칸씩 회전하는 새로운 str를 만들 수가 있다.

2. 괄호의 짝을 확인해 보자

올바른 괄호 문자열인지 체크하기 위해 나는 stack을 사용하였다.
문자열 str의 모든 문자를 순회하면서,
여는 괄호 (, {, [ 의 경우에는 stack에 저장해준다.
닫는 괄호 ), }, ] 의 경우에는 peek()으로 열린 괄호가 stack에 들어가 있는 지 확인 후, 짝이 맞는 열린 괄호가 있다면 pop() 해준다.

그런데 만약, stack이 비어있거나 peek()한 결과가 현재 괄호랑 짝이 맞지 않다면, 올바른 괄호 문자열이 아니게 된다.
이 경우를 만나면 무조건 올바른 문자열이 아니게 되기 때문에, 올바른 문자열인지에 대한 여부를 저장하는 correct변수에다가 false를 저장해 준다.

👾최종 코드

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

        for (int i = 0; i < s.length(); i++) {
            // 스택 생성
            Stack<Character> stack = new Stack<>();
            
			// 올바른 문자열인지에 대한 여부를 저장하는 변수
            boolean correct = true;

            // 회전 중 현재 문자열
            String str = s.substring(i, s.length()) + s.substring(0, i);

            for (int j = 0; j < s.length(); j++) {
                char temp = str.charAt(j);
                switch (temp) {
                    case '(':
                        stack.push(temp);
                        break;
                    case '{':
                        stack.push(temp);
                        break;
                    case '[':
                        stack.push(temp);
                        break;
                    case ')':
                        if (stack.isEmpty() || stack.peek() != '(') {
                            correct = false;
                            break;
                        }
                        else {
                            stack.pop();
                            break;
                        }
                    case '}':
                        if (stack.isEmpty() || stack.peek() != '{') {
                            correct = false;
                            break;
                        }
                        else {
                            stack.pop();
                            break;
                        }
                    case ']':
                        if (stack.isEmpty() || stack.peek() != '[') {
                            correct = false;
                            break;
                        }
                        else {
                            stack.pop();
                            break;
                        }
                }
            }

			// 올바른 문자열인 경우
            if (stack.isEmpty() && correct == true) {
                answer++;
            }
            
            // stack 초기화
            while (!stack.isEmpty()) {
                stack.pop();
            }

        }
        return answer;
    }

올바른 문자열인 경우, correct 변수에는 처음에 저장된 true가 저장되어 있을 것이기 때문에, 조건문을 만들어 answer에 카운트를 증가시켜 주었다.

그리고, 다음 str을 확인하러 가기 위해 stack을 초기화하는 것도 잊지 않고 해주었다.

👾더 나은 코드

import java.util.Stack;

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

        for (int i = 0; i < s.length(); i++) {
            Stack<Character> stack = new Stack<>();
            String str = s.substring(i, s.length()) + s.substring(0, i);
            for (int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                if (stack.isEmpty()) {
                    stack.push(c);
                } else if (c == ')' && stack.peek() == '(') {
                    stack.pop();
                } else if (c == '}' && stack.peek() == '{') {
                    stack.pop();
                } else if (c == ']' && stack.peek() == '[') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
            if (stack.isEmpty()) {
                answer++;
            }
        }

        return answer;
    }
}

여는 괄호의 경우 무조건 stack에 push()해주면 되고,
닫는 괄호의 경우 무조건 peek()값이랑 같다면 즉, 짝이 맞다면 pop()해주면 되기 때문에, 공통되는 부분을 이렇게 간결하게 줄일 수가 있다.

그리고, 올바른 문자열일 경우 stack은 비어있게 되고,
그렇지 않은 경우에는 stack에 요소가 남아있게 되기 때문에,correct 변수를 사용하지 않고 stack이 비어있는 지에 대한 여부만으로도 올바른 문자열인지 아닌지 파악할 수 있다.

---

🔗문제 링크
💻Repository