[프로그래머스] 괄호 회전하기 / Java
문제주소 :programmers.co.kr/learn/courses/30/lessons/76502#
코딩테스트 연습 - 괄호 회전하기
programmers.co.kr
<문제 설명>
문제 설명
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
- (), [], {} 는 모두 올바른 괄호 문자열입니다.
- 만약 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
- 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.
| 0 | "[](){}" | O |
| 1 | "](){}[" | X |
| 2 | "(){}[]" | O |
| 3 | "){}[](" | X |
| 4 | "{}[]()" | O |
| 5 | "}[](){" | X |
- 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.
입출력 예 #2
- 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.
| 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