[ 알고리즘 ] 코딩 - Programmers - 괄호 회전하기.java

---

문제 링크

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

코딩테스트 연습 - 괄호 회전하기

---

문제 개요

프로그래머스 - Level 2 - (자바) 괄호 회전하기 - 스택 / 문자열 다루기

문제 설명

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

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

회전 예시

---

로직

for문 2개로 해결.

Step 01. 1번 for 반복에서는 가장 앞의 문자를 확인한다. 닫는 괄호라면 넘기고 여는 괄호인 경우에만 스택에 쌓는다.

Step 02. 스택이 빈 경우 닫는 괄호라면 넘기고, 여는 괄호라면 스택에 넣어준다. 스택이 비어있지 않은데 닫는 괄호가 들어온다면 스택을 조사하고 가능한지 판단한다.

Step 03. 다음으로 넘어가는 경우 문자열의 가장 앞 문자를 가장 뒤로 넘긴다.

Step 04. Step 01 ~ Step 03을 문자열의 길이만큼 반복하면 정답!

---

코드

import java.util.Stack;
class Solution {
		public int solution(String s) {
			int length = s.length();
			int answer = 0;
			StringBuilder sb = new StringBuilder(s);
			for (int i = 0; i < length; i++) {
				boolean isPossible = true; // 가능한지 판단
				Stack<Character> stack = new Stack<Character>();
				char first_c = sb.charAt(0); // 가장 앞의 괄호
				// 닫는 괄호가 처음에 오면 어떤 경우도 불가능
				if(first_c == ']' || first_c == '}' || first_c == ')') {
					// 가장 앞자리 괄호를 뒤로 넘기고 다음으로
					char first = sb.charAt(0);
					sb.deleteCharAt(0);
					sb.append(first);
					continue;
				}
				// 여는 괄호라면 스택에 적재
				stack.push(first_c);
				// 2번째 괄호부터 조사
				for (int j = 1; j < length; j++) {
					char cur_c = sb.charAt(j);
					if (stack.isEmpty()) { // 스택이 빈 경우
						// 닫는 괄호가 처음이면 무조건 불가능
						if(cur_c == ']' || cur_c == '}' || cur_c == ')') {
							isPossible = false;
							break;
						}
						stack.push(cur_c);
						// 여는 괄호면 일단 적재
					} else if (cur_c == '[' || cur_c == '{' || cur_c == '(') {
						stack.push(cur_c);
					} else { // 빈 상태가 아닌데 닫는 괄호인 경우
						char pre_c = stack.peek();
						switch (pre_c) { // 짝 조사
						case '[':
							if (cur_c == ']')
								stack.pop();
							else
								isPossible = false;
							break;
						case '(':
							if (cur_c == ')')
								stack.pop();
							else
								isPossible = false;
							break;
						case '{':
							if (cur_c == '}')
								stack.pop();
							else
								isPossible = false;
							break;
						}
					}
					if (!isPossible)
						break;
				}
				// 현재 스택에 괄호가 없는 상태에만 가능
				if (isPossible && stack.isEmpty())
					answer++;
				// 가장 앞자리 뒤로 넘김
				char first = sb.charAt(0);
				sb.deleteCharAt(0);
				sb.append(first);
			}

			return answer;
		}
	}