다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
()
, []
, {}
는 모두 올바른 괄호 문자열입니다.A
가 올바른 괄호 문자열이라면, (A)
, [A]
, {A}
도 올바른 괄호 문자열입니다. 예를 들어, []
가 올바른 괄호 문자열이므로, ([])
도 올바른 괄호 문자열입니다.A
, B
가 올바른 괄호 문자열이라면, AB
도 올바른 괄호 문자열입니다. 예를 들어, {}
와 ([])
가 올바른 괄호 문자열이므로, {}([])
도 올바른 괄호 문자열입니다.대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s
가 매개변수로 주어집니다. 이 s
를 왼쪽으로 x (0 ≤ x < (s
의 길이)) 칸만큼 회전시켰을 때 s
가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.
s | result |
---|---|
"{}" | 3 |
"}]()[{" | 2 |
"[)(]" | 0 |
"}}}" | 0 |
입출력 예 #1
"[](){}"
를 회전시킨 모습을 나타낸 것입니다.x | s를 왼쪽으로 x칸만큼 회전 | 올바른 괄호 문자열? |
---|---|---|
0 | "{}" | O |
1 | "](){}[" | X |
2 | "(){}[]" | O |
3 | "){}[](" | X |
4 | "{}" | O |
5 | "}{" | X |
입출력 예 #2
"}]()[{"
를 회전시킨 모습을 나타낸 것입니다.x | s를 왼쪽으로 x칸만큼 회전 | 올바른 괄호 문자열? |
---|---|---|
0 | "}]()[{" | X |
1 | "]()[{}" | X |
2 | "()[{}]" | O |
3 | ")[{}](" | X |
4 | "{}" | O |
5 | "{}]()[" | X |
입출력 예 #3
입출력 예 #4
이번 문제는 자료구조 선택과 알고리즘 작성에 시간이 좀 걸렸다. 괄호들을 다른 형태로 치환해서 풀어보려고도 했는데, 결국 괄호는 그대로 둔 상태로 최초에 “ ( , { , [ ”
가 들어오는 경우에만 Queue
에 넣고 그 후로 오는 값들을 치환해서 푸는 방식으로 넘었다.
하지만 Queue는 선입선출 방식으로 뒤에 오는 값들과의 비교 & 삭제를 진행하기에 좋은 자료구조가 아님을 깨닫고 Deque로 변경하였다.
“ ( , { , [ ”
가 들어간 이후로 “ ) , } , ] “
가 들어오면 이를 다시 “ ( , { , [ ”
로 치환하여 Deque
내부에 같은 값이 있다면 제거해주는 방식으로 진행하였는데, 이것도 하다보니 굳이 Deque
를 사용할 필요 없이 선입후출 방식인 Stack
을 사용하면 된다는 것을 깨달았다.
또한, 문자열을 회전 시켜주는 방법도 Deque
를 사용할 때에는 임시 변수에 poll()
값을 담아주고 다시 add()
하는 방식으로 회전 시켰지만, Deque
를 사용하지 않게 되었으니, String.substring()
과 charAt()
을 통해 회전을 시켜주었다.
import java.util.*;
class Solution {
public int solution(String s) {
int answer = 0;
if (check(s)) {
answer++;
}
for (int i = 1; i < s.length(); i++) {
System.out.println(i);
s = rotate(s);
if (check(s)) {
answer++;
}
}
return answer;
}
public String rotate(String s) {
s = s.substring(1) + s.charAt(0);
return s;
}
public boolean check(String s) {
Stack<Character> stack = new Stack<>();
// ({})[]
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else if (!stack.isEmpty()) {
switch (c) {
case ')':
compare(stack, '(');
break;
case '}':
compare(stack, '{');
break;
case ']':
compare(stack, '[');
break;
}
} else {
stack.push(c);
}
System.out.println("stack = " + stack);
}
return stack.isEmpty();
}
public void compare(Stack<Character> stack, char c) {
if (stack.peek() == c) {
stack.pop();
}
}
}