문제 요약
소괄호, 중괄호, 대괄호로 이뤄진 문자열이 주어진다. 아래 조건을 충족하면 올바른 괄호라고 여기며,
s의 길이만큼 왼쪽 회전을 시킬 때s가 올바른 괄호 문자열이 되는 회전 횟수를 반환하자
- (), [], {} 는 모두 올바른 괄호 문자열입니다.
- 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
- 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
[ 예시 ]
| s | return |
|---|---|
| "[)(]" | 0 |
| "}]()[{" | 2 |
[ 제약 조건 ]
- 1 ≤
s.length()≤ 1,000
[ 프로그래머스 ]
풀이
stack을 통해 닫힌 괄호가 오기 전, 열린 괄호가 있었는지 확인하고,ArrayList을 통해 괄호가 회전하도록 구상했다.
(1) 입력값 s를 ArrayList에 모두 넣는다.
(2) ArrayList에서 꺼낸 요소가 [이거나 {, (인 경우, stack에 넣는다.
(3) 만일 ], }, )와 같이 닫힌 괄호를 만난 경우, stack에서 pop()을 통해 이전 요소를 꺼내어 같은 괄호인지 확인한다.
(4) 만약 같지 않다면, false를 반환하고, 같은 괄호계열인 경우 함께 묶여 없앤다.
- 예를 들어, stack에
{(이 있는 상태에서)가 들어오면()로 완성될 수 있기에 stack에는{만 남게 된다.
(5) (2)~(4)과정을 반복한 후, 올바른 괄호라면 stack이 비게 되며 그렇지 않다면, false를 반환한다.
(6) (2)~(4)의 결과 혹은 (5)의 결과가 false가 아닌 경우 answer 값을 증가시킨다
(7) ArrayList의 가장 앞 요소를get(0)을 통해 얻고,remove(0)한 후,add(0)을 하여 뒤로 보내 회전 시킨디ㅏ.
(8) 위 과정을s.length()만큼 반복한다.
Code
import java.util.*;
class Solution {
static ArrayList<String> list;
public int solution(String s) {
int answer = 0;
list = new ArrayList<>();
for(int i=0;i<s.length();i++) {
list.add(s.substring(i, i+1));
}
int x = 0;
while (x < s.length()) {
if (solve(s))
answer++;
list.add(list.get(0));
list.remove(0);
x++;
}
return answer;
}
private static boolean solve(String s) {
Stack<String> stack = new Stack<>();
for(int i=0;i<s.length();i++) {
String tmp = list.get(i);
try{
switch (tmp) {
case "[":
case "{":
case "(":
stack.push(tmp);
break;
case "]":
if (!stack.pop().equals("[")) return false;
break;
case "}":
if (!stack.pop().equals("{")) return false;
break;
case ")":
if (!stack.pop().equals("(")) return false;
break;
}
} catch (Exception e) {
return false;
}
}
if (stack.isEmpty())
return true;
return false;
}
}시도
괄호의 개수로 확인하기
이와 비슷한 문제 올바른 괄호 문제에서 풀었던 것처럼 각 괄호 계열의 개수로 판별했다가 {(})와 같은 반례의 벽에 막히고 말았다. 그래도 좋은 시도였다 :)
import java.util.*;
class Solution {
static ArrayList<String> list;
public int solution(String s) {
int answer = 0;
list = new ArrayList<>();
String[] tmp = s.split("");
for(int i=0;i<tmp.length;i++) {
list.add(tmp[i]);
}
int x = 0;
list.add(list.get(x));
list.remove(x);
while (x < tmp.length) {
if (solve(s))
answer++;
list.add(list.get(0));
list.remove(0);
x++;
}
return answer;
}
private static boolean solve(String s) {
int large = 0; //대괄호
int mid = 0; //중괄호
int small = 0; //소괄호
for(int i=0;i<list.size();i++) {
String tmp = list.get(i);
switch (tmp) {
case "[": large++; break;
case "]": large--; break;
case "{": mid++; break;
case "}": mid--; break;
case "(": small++; break;
case ")": small--; break;
}
if (large < 0 || mid < 0 || small < 0)
return false;
if ()
}
if (large > 0 || mid > 0 || small > 0)
return false;
return true;
}
}느낀점
원래 챌린저 문제를 풀어야하는데, 각 난이도별 사람이 모인 곳에 가니 아무도 없어 외로움에 옆 방 미들러 방으로 넘어갔다. 뭔가 챌린저 풀기엔 아직 이른 것 같으면서도 미들러 풀기엔 뭔가 아쉬운 그런 애매한 어딘가에 혼자 있는 느낌이다. ㅠ
그래도 이왕 할 꺼면 깨지고 부숴지는 게 나을 거 같아, 내일은 오늘 못 푼 챌린저 문제를 풀어볼 예정이다.
이 또한 지나가리라