프로그래머스 월간 코딩테스트 시즌2 (4월)의 2번문제에 대한 리뷰입니다
옳바른 괄호에 대한 설명과 함께 괄호들일 얽혀있는 문자열을 입력으로 줍니다.
주어진 문자열의 크기가 N이라고 하면, 0부터 N-1까지 문자열을 순환시키면서 해당 문자열이 옳바른 괄호를 갖는지 확인하고 옳바른 괄호가 됐을때의 방법의 수를 리턴하는 문제입니다
문제에서 제시하는 옳바른 괄호란
괄호 문자열 ()과 {}가 있을 때, (){}도 옳바른 문자열, ({})도 옳바른 문자열이라고 정의하고 있습니다.
즉, 괄호가 옳바르게 묶여있는 문자열일 경우에 정답을 한개씩 증가시키면 됩니다.
저는 괄호가 옳바르게 묶여있는지 판단할 때 가장 좋은 방법은 스택을 이용하는 방법이라고 생각하였고, 스택 계산기를 응용하여 문제를 풀었습니다
Stack(스택)
스택은 FILO(First In Last Out)의 특징을 가진 자료구조로, 가장 빠르게 넣은 데이터가 가장 늦게나오는 형태입니다.
그래서 스택은 짝을 매칭시킬 때 유용하게 쓰일 수 있습니다.
스택의 가장 상단에 나와 매칭되는 짝이 있다는건, 가장 최근에 넣은 데이터가 매칭이 될 수 이
Stack Calculator Code
스택 계산기는 다음의 순서로 구현합니다.
- 여는 괄호는 스택에 push
- 닫힌 괄호가 나왔을 때, 스택의 상단에 매칭되는 여는 괄호가 있다면 pop
- 스택의 크기가 0인데 닫힌 괄호가 나오거나, 상단의 요소와 닫히는 괄호가 매칭이되지 않는다면 매칭되지 않는 문자열
public class Solution{
// 시스템에서 괄호 문자열을 매개변수로 입력
public int solution(String s){
StringBuffer sb = new StringBuffer(s);
int answer = 0;
for(int i = 0; i < sb.length(); i++){
// 문자열 순환
sb.append(sb.charAt(0));
sb.deleteCharAt(0);
if(chk(sb.toString()){
answer++;
}
}
return answer;
}
public boolean chk(String s){
Stack<Character> stack = new Stack<>();
for (char tmp : str.toString().toCharArray()) {
if (tmp == '[' || tmp == '{' || tmp == '(') {
stack.push(tmp);
} else if (!stack.isEmpty()) {
char sTop = stack.peek();
if (sTop == '[' && tmp == ']')
stack.pop();
else if (sTop == '{' && tmp == '}')
stack.pop();
else if (sTop == '(' && tmp == ')')
stack.pop();
else
// 괄호가 올바르게 매칭되지 않음
return false;
} else {
// stack의 크기가 0일 때, 제거하려 하였으므로 괄호가 제대로 매칭되지 않는 것
return false;
}
}
if (stack.isEmpty())
return true;
else
// 스택에 내용물이 남아있다는건 올바르게 매칭되지 않았다는 것
return false;
}
}코드에서는 chk()메서드가 스택 계산기 입니다.
먼저 열리는 괄호([,{,()일 때는 스택에 push합니다
하지만 닫히는 괄호(],},))일 때는 2가지 상황으로 분기가 됩니다
- 스택이 비어있지 않을 때
- 스택이 비어있을 때
스택이 비어있지 않을 때는 스택의 가장 상단에 있는 원소를 확인합니다. 현재 들고있는 닫히는 괄호와 짝이되는 열린 괄호가 스택의 상단에 있다면 옳바르게 매칭된 상황이므로 삭제하고 다음 반복문으로 진행합니다.
하지만 매칭되지 않는다면
또한, 스택이 비어있는데 닫히는 괄호가 나와 스택에서 원소를 빼야하는 상황은 문제에서 정의한 옳바른 괄호가 아닙니다.
