[Programmers/Java]프로그래머스 연습문제 - 괄호 회전하기

문제링크

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 해야 합니다.

 

풀이

Stack과 Queue를 사용하자는 생각이 들었습니다.

Stack : 선입후출 , Queue : 선입선출

괄호는 계속 순서를 지키며 회전해야하고, 이때 올바른 괄호 구조인지 체크해야합니다.

Queue에 넣어서 괄호 자체를 회전시키고, Stack을 이용해서 peek()로 마지막 값을 확인하여 원하는 값이 맞는지 체크를 하며 괄호를 돌립니다.

 

작성코드

import java.util.*;
class Solution {
    public int solution(String s) {
                //괄호가 잘 닫겨야함! stack을 사용해서 풀어보자
        int answer = 0;
        Queue<String> queue = new LinkedList<>();

        for(int i = 0; i < s.length(); i++){
            String str = s.substring(i,i+1);
            queue.add(str);
        }
        for(int i=0;i<s.length();i++) {
            String firstS = queue.poll();
            queue.add(firstS);
            Stack<String> stack = new Stack<>();
            for (int j = 0; j < s.length(); j++) {
                String otherS = queue.poll();//맨앞거 빼고 나머지애들을 빼냄
                queue.add(otherS);
                if (stack.isEmpty()) {
                    stack.push(otherS);
                } else if (otherS.equals(")") && stack.peek().equals("(")) {
                    //남은 것이 stack에 짝과 맞을 경우
                    stack.pop();
                } else if (otherS.equals("]") && stack.peek().equals("[")) {
                    //남은 것이 stack에 짝과 맞을 경우
                    stack.pop();
                } else if (otherS.equals("}") && stack.peek().equals("{")) {
                    //남은 것이 stack에 짝과 맞을 경우
                    stack.pop();
                }else{
                    stack.push(otherS);
                }
            }
            if(stack.isEmpty()){
                answer++;
            }
        }

        return answer;
    }
}