문제 url:
괄호
문제:
🤔 문제 알아보기
이번 문제는 조금 고민을 해볼 필요가 있던 문제였다.
먼저 문제를 간략히 요약한다면, () -> 이런 형태로 된 것이 VPS이다.
하지만, ()) -> 이런 형태는 VPS가 아니다.
즉! () 이런 형태로 괄호가 잘 닫혀있다면 VPS 그렇지 않은 모든 형태는 VPS가 아닌 것이다.
이를 이해해서 푼다면,
현재 입력이 ')' 이며, 어느 공간에 이전 값이 '(' 으로 저장되어 있다면 '('를 제거하고 ')'를 공간에 저장시키지 않으면 된다.
이렇게 적으니 이해가 되지 않을 수 있는데, 스택을 활용하면 이해가 쉬울 것이다.
즉, 스택에 ((( 이런식으로 값을 저장시켜놓고, 스택 최상단 값이 '('이며 입력값이 ')'라면, pop()메서드를 사용하고 그렇지 않으면 입력값을 하나씩 push()하며 저장시키면 된다.
만약 입력받은 값이 VPS라면, 스택 공간은 비어있을 것이며 그렇지 않으면 데이터가 존재할 것이다.
이를 이용해서 문제를 풀어보자.
※스택에 대해서 잘 모르는 분을 위해 아래 링크를 확인한 후 다시 보면 이해가 더 될 것이다.
[Java] 스택(stack) 클래스 정리 & 사용법
🐱👤 실제 코드
import java.io.*;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int i = 0; i < tc; i++) {
Stack<Character> stack = new Stack<>();
String str = br.readLine();
stack.push(str.charAt(0));
for(int j = 1; j < str.length(); j++) {
char word_idx;
if(!stack.empty()) {
word_idx = stack.peek();
} else {
word_idx = 0;
}
if(word_idx == '(' && str.charAt(j) == ')') {
stack.pop();
} else {
stack.push(str.charAt(j));
}
}
if(stack.empty()) {
sbd.append("YES").append("\n");
} else {
sbd.append("NO").append("\n");
}
}
System.out.println(sbd);
}
}
특별히 코드에서 어려운 부분이 없지만 그래도 하나씩 살펴보자면,
stack.push(str.charAt(0));
for(int j = 1; j < str.length(); j++) {
char word_idx;
if(!stack.empty()) {
word_idx = stack.peek();
} else {
word_idx = 0;
}j를 1부터 하기 위해 처음에 먼저 첫번쨰 단어를 스택에 넣는다.
그 후, word_idx라는 이전값을 저장하는 변수를 정의하고, 스택에 데이터가 존재한다면, 최상단 값을 해당 변수에 저장한다.
여기서 최상단 값을 넣는 이유는 결국 최상단 값이 이전값이 될 것이며 또한 '()' 형태가 만들어져 없어지면 그 다음 최상단값과 입력값을 비교해야 하기 때문이다.
여기서 word_idx = 0을 넣는 이유는, 의미없는 값을 넣는 작업이니 특별하지 않다.
if(word_idx == '(' && str.charAt(j) == ')') {
stack.pop();
} else {
stack.push(str.charAt(j));
}그 후, 최상단값 혹은 이전값이 '('이며 현재 단어가 ')'라면, 이전 값을 제거해 '()'형태로 소거시키며 그렇지 않다면 스택에 저장하는 구조이다.
코드쪽으론 특별히 어려운 것이 없기 때문에 여기서 정리를 마친다
🤢 리팩토링
문제를 푼 후, 힌트에서 그리디 방식으로 풀 수 있다는 것을 보고 이를 또 풀어봤는데,
위의 형태와 비슷하게 접근하면 충분히 생각할 수 있는 문제이다.
위에서 stack이 비어있다면 VPS라고 했는데, 이것도 마찬가지로 현재 카운트가 0이면 VPS라고 정의하면 되는 것이다.
그럼 어떻게 이를 이용해 풀 수 있는가?
'(' 가 나오면 count++을 하고 ')'가 나오면 count--를 하면 된다.
그렇게 되면 만약 완전한 VPS가 나오면 같은 짝을 이루니 카운트가 0이 될 것이다.
근데 반례로 () () () )( 이렇게 나오면 어떡할것인가?
분명 다 더하면 count는 0이 될 것이다. 하지만 오답이다. 왜? vps가 아니기 때문인데,
해당 예외처리도 간단히 생각하면 복잡하지 않다. count가 3번째 VPS까지 가면 0이 될 것이다. 그 다음에 ')'를 통해 카운트는 곧 음수가 될 것인데, 이때 반복문을 빠져나가면 된다.
어차피 ')' 이 단어가 떠서 음수가 된 이상 해당 문자열은 완전한 VPS가 되지 못하기에 가능하다.
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int i = 0; i < tc; i++) {
String str = br.readLine();
int cnt = 0;
for(int j = 0; j < str.length(); j++) {
if(str.charAt(j) == '(') {
cnt++;
} else {
cnt--;
}
if(cnt < 0) {
break;
}
}
if(cnt == 0) {
sbd.append("YES").append("\n");
} else {
sbd.append("NO").append("\n");
}
}
System.out.println(sbd);
}
}
코드 역시 간단하기 때문에 따로 설명하지 않겠다.
그리디 방법이 더 간단해 시간, 메모리도 적게 들 것이라고 생각했는데 큰 차이가 없다...
