들어가며
- VPS는 기본 문자열 쌍으로 괄호가 올바르게 배치되어 있는가를 확인하는 문제이다.
- 이때 올바르게 배치되었다 라는 상태의 정의는 괄호의 ( 과 ) 가 쌍을 이룰 수 있도록 배치되어 있는 상태를 말한다.
- 예시를 들어 (())라는 괄호 쌍은 올바르게 배치되었다. ( 와 )가 쌍을 잘 이루고 있기 때문이다.
- 다른 예시로 (())((는 올바르지 않은 배치이다. 뒤의 ((의 쌍이 존재하지 않기 때문이다.
- 다른 예시로 )(는 올바르지 않은 배치이다. 닫힌 괄호가 먼저 나와있기 때문이다.
- String 배열로 문자열들이 들어온다. 문자열들은 모두 ( 또는 )로 이루어져 있으며 다른 입력이 들어오는 경우는 존재하지 않는다. 이때 각 문자열들이 VPS로 올바르게 배치되었는지 확인하여 그 결과를 배열로 반환하는 함수를 구현하는것이 문제이다.
import java.util.*;
public class UserSolution {
public static void main(String[] args){
String[] dataSet = {"()()(())(((()))())", "()", ")(", "((())()()))((())()(())", "(())(())()()"};
boolean[] result = solution(dataSet);
for (boolean element: result){
System.out.println(element);
}
}
static boolean[] solution(String[] dataSet){
}
}
접근 방법
- 단순하게 생각하여 접근하면 닫힌 괄호가 입력으로 들어올 때 이전에 돌아봤던 괄호들 중 쌍이 되지 않고 열린 괄호가 있는지를 찾으면 된다.
- 해당 방법은 잘 들어맞는것 처럼 보인다. 하지만 이전에 탐색했던 모든 문자열들을 다시 살펴봐야 하기 때문에 해당 방법은 길이가 길어지면 사용하기 힘든 방법이 된다.
- 그렇다면 스택을 사용하는 방법을 생각해보자. 그럼 스택을 어떻게 사용해야 할까
- VPS의 기본적인 성립 조건은 쌍이 모두 이루어질 수 있는가이다. 따라서 열린 괄호를 스택에 넣고, 닫힌 괄호가 입력으로 들어올 시 스택을 검사하여 열린 괄호가 존재한다면 이 두 괄호는 쌍이 될 수 있다는 것이다.
- 쌍이 완성되는 괄호이기 때문에 더 이상 검사할 필요가 없다. 따라서 스택에서 해당 열린 괄호를 제거한다.
- 만약 문자열이 모두 끝났다면 그 시점에서 스택에 괄호가 남겨져 있을 시 열린 괄호에 쌍이 될 닫힌 괄호가 존재하지 않는다는 것이므로 해당 문자열은 VPS가 아니다.
- 문자열이 모두 끝난 시점에서 괄호가 남겨져 있지 않다면 모든 열린 괄호에 쌍이 될 닫힌 괄호가 존재한다는 것이므로 VPS이다.
- 위 로직을 짠 코드는 아래와 같다.
import java.util.*;
public class UserSolution {
public static void main(String[] args){
String[] dataSet = {"()()(())(((()))())", "()", ")(", "((())()()))((())()(())", "(())(())()()"};
boolean[] result = solution(dataSet);
for (boolean element: result){
System.out.println(element);
}
}
static boolean[] solution(String[] dataSet){
boolean[] result = new boolean[dataSet.length];
for (int i = 0; i < dataSet.length; i++){
Deque<Character> stack = new ArrayDeque<>();
boolean res = true;
for (int j = 0; j < dataSet[i].length(); j++){
if (dataSet[i].charAt(j) == ')'){
if (stack.isEmpty()){
res = false;
break;
} else{
if (stack.peekLast() == '('){
stack.pollLast();
} else{
res = false;
break;
}
}
} else{
stack.addLast(dataSet[i].charAt(j));
}
}
res = res && stack.isEmpty();
result[i] = res;
}
return result;
}
}
- 각 문자열을 탐색하며 열린 괄호인지 닫힌 괄호인지를 확인하고 그에 맞는 연산을 수행한다.
- 위에서 설명한 괄호쌍이 맞지 않는 경우가 나온다면 VPS가 아니기 때문에 false를 배열에 넣고, 모든 조건을 통과하여 VPS라는 것이 증명되면 true를 배열에 넣는다.