괄호 회전하기 (Java)
괄호 회전하기 - Level 2
https://school.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 이하입니다.
입출력 예
| s | result |
| "[](){}" | 3 |
| "}]()[{" | 2 |
| "[)(]" | 0 |
| "}}}" | 0 |
이 문제는 주어지는 문자열을 한칸씩 옆으로 이동시키면서
각, 문자열의 형태가 올바른 괄호인지를 알아보는 문제입니다.
첫번째 예제를 보겠습니다.
| s | s를 왼쪽으로 x칸만큼 회전 | 올바른 괄호 문자열? |
| 0 | "[](){}" | O |
| 1 | "](){}[" | X |
| 2 | "(){}[]" | O |
| 3 | "){}[](" | X |
| 4 | "{}[]()" | O |
| 5 | "}[](){" | X |
위에 나온 것처럼 1번 예제의 총 count는 3가지입니다.
일단 먼저 괄호 회전을 구현해보겠습니다.
문자열 형태로 넘어오는 것이기 때문에,
첫번째 값을 마지막 값으로 넘겨주면서 진행하였습니다.
s = s.substring(1,s.length()-1)+s.charAt(0);
이런 코드를 삽입한다면, 위의 그래프처럼 값이 나올 것입니다.
괄호관련 문제에서 가장 자주 쓰이는 것이 바로 Stack입니다.
올바른 괄호를 찾기 위해서는 여는 괄호와 닫는 괄호가 차례로 들어와야 합니다.
1번 예제의 첫번째 문자열을 확인해보겠습니다.
"[](){}"
| s.charAt(i) | Character |
Stack
|
Stack.size()
|
| 0 | [ | push | 1 |
| 1 | ] | pop | 0 |
| 2 | ( | push | 1 |
| 3 | ) | pop | 0 |
| 4 | { | push | 1 |
| 5 | } | pop | 0 |
이렇게 진행한 후, Stack.size()==0 이면 경우의 수를 증가시켜줍니다.
실패하는 경우의 수를 확인해보겠습니다.
"](){}["
| s.charAt(i) | Character |
Stack
|
Stack.size()
|
| 0 | ] | X | X |
| 1 | ( | ||
| 2 | ) | ||
| 3 | { | ||
| 4 | } | ||
| 5 | [ |
첫번째의 닫는 괄호가 들어오면서 더이상 진행할 이유가 없기 때문에
함수 자체를 종료하게 구현해놓았습니다.
만약, 무시하고 진행을 한다고 하더라도
1,2,3,4번째 들어오는 값들은 제거되어서 없어지겠지만
0, 5번째에 들어오는 값들은 남아있으므로
Stack.size()!=0이기 때문에 경우의 수 카운트를 하지 않습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
import java.util.Stack;
class Solution {
public int solution(String s) {
int answer = 0;
for(int i = 0;i<s.length();i++) {
if(check(s)) answer++;
s = s.substring(1,s.length())+s.charAt(0);
}
return answer;
}
static boolean check(String s){
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()){
switch(c) {
case '(': stack.add(c); break;
case '{': stack.add(c); break;
case '[': stack.add(c); break;
case ')':
if(stack.isEmpty() || stack.peek()!='(') return false;
stack.pop();
break;
case '}' :
if(stack.isEmpty() || stack.peek()!='{') return false;
stack.pop();
break;
case ']' :
if(stack.isEmpty() || stack.peek()!='[') return false;
stack.pop();
break;
}
}
return stack.isEmpty() ? true : false;
}
}
|
cs |