[프로그래머스] 괄호 회전하기

문제

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

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

문제 출처

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

생각

• 주어진 문자열을 한칸씩 회전시켜가면서 회전된 문자열이 각각 올바른 괄호인지 판단하자
• 올바른 괄호인지 판단하려면?
  • [] 또는 {} 또는 () 를 빈칸으로 replace를 계속 했을 때 아무것도 남지 않으면 올바른 괄호
  • 반복 횟수?
    • 최대 = {[()]} 이런 식으로 다 겹쳐 있을 때 가장 반복 횟수가 많으므로 s의 길이 / 2

코드

class Solution {
    public int solution(String s) {
        int answer = 0;
        for (int i = 0; i < s.length(); i++){
            answer += isCorrect(s.substring(i) + s.substring(0,i));
        }
        return answer;
    }
    
    private int isCorrect(String s){
        int cnt = s.length() / 2;
        while (s.length() > 0 && cnt > 0 ){
            s = s.replace("[]","").replace("{}","").replace("()","");
            cnt--;
        }
        return s.length() > 0 ? 0: 1;
    }
}

다른 사람의 풀이

import java.util.Stack;

class Solution {
    private final Stack<Character> stack = new Stack<>();

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

            for (int i = 0; i < s.length(); i++) {
                stringBuilder.append(stringBuilder.charAt(0));
                stringBuilder.deleteCharAt(0);
                if (correctParenthesis(stringBuilder.toString().toCharArray()))
                    answer++;
            }
            return answer;
        }

        private boolean correctParenthesis(char[] s) {
            for (char c : s) {
                if (!(check(c, '(', ')') && check(c, '[', ']') && check(c, '{', '}')))
                    return false;
            }
            return stack.isEmpty();
        }

        private boolean check(char c, char a, char b) {
            if (c == a)
                stack.push(a);
            else if (c == b)
                if (!stack.isEmpty() && stack.peek() == a) stack.pop(); else return false;
            return true;
        }
}

• 문자열 replace 대신 stack을 이용해서 올바른 괄호인지 판별한 풀이를 기록한다
• 나의 풀이보다 조금 더 복잡해 보이지만 속도 측면에서 훨씬 더 빨랐다 😳😳