2 분 소요

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/76502

문제 제목 : 괄호 회전하기

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

(), [], {} 는 모두 올바른 괄호 문자열입니다. 만약 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 해야 합니다. ※ 공지 - 2021년 4월 16일 테스트케이스가 추가되었습니다.

문제 풀이

import java.util.*;

class Solution {
    // 반환 = s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수
    public int solution(String s) {
        int answer = 0; // 올바른 괄호 문자열이 되는 경우의 수를 저장할 변수

        // s를 0부터 s.length()까지 회전하며 탐색
        for(int x = 0; x < s.length(); x++){
            Stack<Character> stack = new Stack<>(); // 괄호를 저장할 스택 생성
            String str = s.substring(x, s.length()) + s.substring(0, x); // x만큼 왼쪽으로 회전한 문자열 생성

            // 회전한 문자열을 순회하며 괄호를 검사
            for(int i = 0; i < str.length(); i++){
                char c = str.charAt(i); // 문자열의 i번째 문자 가져오기
                if(stack.isEmpty()){ // 스택이 비어있으면
                    stack.push(c); // 현재 문자를 스택에 넣음
                }
                else if(stack.peek() == '(' && c == ')'){ // 스택의 가장 위에 있는 괄호가 '('이고 현재 문자가 ')'이면
                    stack.pop(); // 스택에서 '('를 제거
                }
                else if(stack.peek() == '[' && c == ']'){ // 스택의 가장 위에 있는 괄호가 '['이고 현재 문자가 ']'이면
                    stack.pop(); // 스택에서 '['를 제거
                }
                else if(stack.peek() == '{' && c == '}'){ // 스택의 가장 위에 있는 괄호가 '{'이고 현재 문자가 '}'이면
                    stack.pop(); // 스택에서 '{'를 제거
                }
                else{ // 위의 조건들에 해당하지 않으면
                    stack.push(c); // 현재 문자를 스택에 넣음
                }
            }
            if(stack.isEmpty()){ // 스택이 비어있으면
                answer++; // 올바른 괄호 문자열이 되는 경우의 수 증가
            }
        }
        return answer; // 결과 반환
    }
}

댓글남기기