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

문제주소 :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 이하입니다.

---

입출력 예

sresult

"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

---

입출력 예 설명

입출력 예 #1

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

xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열?

0	"[](){}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}[]()"	O
5	"}[](){"	X

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

입출력 예 #2

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

xs를 왼쪽으로 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일 테스트케이스가 추가되었습니다.

 

<풀이법>

▒ 한줄 개념: 스택 ▒ 

전형적인 올바른 괄호 문제에 문자열 변형이 추가된 문제이다.

 

1. 괄호들로만 이루어진 문자열이 나열되어 있을 때, 이 문자열이 올바른 괄호 순서로 구성되어있는지 파악한다.

2. 문자열을 한칸 이동(회전)을 시켜서, 다시 1번을 진행한다. 이때, 회전은 문자열 길이만큼 진행한다(원래 문자열이 나타나기 전까지).

 

[1]

괄호 회전에 대해서 가장 쉬운 풀이법은 스택을 사용하는 것이다. 여는 괄호( '[', '{', '(' ) 가 나왔을 경우에는 스택에 추가해주고, 닫는 괄호( ']', '}', ')' )가 나왔을 경우에는 스택의 맨 위를 확인하고, 자신과 맞는 여는 괄호일 경우 스택에서 pop해준다. 만약 아니면, 괄호 순서가 잘못된 것이니 이 문자열은 틀린문자열이 된다.

 

이를 확인하는데 있어 스위치문을 사용해주었다. 또한 닫는 괄호의 경우 우선 peek()함수를 이용해 스택의 맨 위 글자를 확인해주는데, 이 때 스택이 비어있는 경우 에러가 발생할 수 있어 try-catch를 이용해 false를 바로 리턴하도록 해주었다. 여기서 에러가 발생하는 경우는 여는 괄호 이전에 닫는 괄호가 먼저나오는 경우( "}{" ) 이므로, 무조건 false가 된다.

 

[2]

문자열을 회전시키는 것은, 단순히 substring을 통해 문자열의 첫번째를 잘라내고, 이를 맨 뒤에 붙여주면 된다. 본래 문자열이 나오기 이전까지 반복하면 되므로, 단순 문자열의 길이만큼 반복문을 써주면 편하다.

 

 

<코드(Java)>

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        String new_s = s;
        for(int i = 0; i < s.length(); i++){
            if(checkString(new_s)) answer++;
            new_s = new_s.substring(1, s.length()) + new_s.charAt(0);
        }
        
        return answer;
    }
    
    boolean checkString(String s){
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            try{
                switch(s.charAt(i)){
                    case '[': 
                        stack.add('[');
                        break;
                    case ']':
                        if(stack.peek() != '[') return false;
                        stack.pop();
                        break;
                    case '{': 
                        stack.add('{');
                        break;
                    case '}':
                        if(stack.peek() != '{') return false;
                        stack.pop();
                        break;
                    case '(': 
                        stack.add('(');
                        break;
                    case ')':
                        if(stack.peek() != '(') return false;
                        stack.pop();
                        break;
                }
            } catch(Exception e){
                return false;
            }
        }
        return stack.isEmpty() ? true : false;
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest