이번 글에서는 4949번 문제를 통해 스택을 활용,
괄호의 균형을 맞춰완벽한 문장을 나타내 보자.
문제 핵심
- 문자열은 ( ), [ ] 이 두 소괄호와 대괄호가 짝을 이루어야 한다.
- 1 : 1 매칭만 가능하다.
- 공백 이후의 . 과 같은 괄호가 없는 문장도 균형 잡힌 문자열이다.
- (, [ 이 나온 후에 ), ] 가 나와야 짝이 이루어 진다.
- ] [ 은 짝이 아닌 경우
풀이 과정
먼저 우리가 찾아야 할 것은 괄호들이다.
이는 StringTokenizer를 활용해 볼 예정이다. ( 물론 chatAt()을 사용하면 더 빠르다. )
다음 자료구조 스택에 대한 글과 split과 StringTokenizer비교에 관한 글을 참고하면 좋을 것 같다.
스택 ( 자료구조 ) - JAVA
오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.접시를 쌓아올린다고 생각하면 된다.스택 ( Stack )후
p-coding.tistory.com
[ JAVA ] 문자열 자르기 Splite VS StringTokenizer
문자열을 특정 구분자로 분리할 수 있는 StringTokenizer와 Splite을 사용하던 중구체적인 차이점이 무엇인지 궁금하여 조사하게 되었다.메모리에서 장점을 가진다고 하지만 정확히 어떤구조로 작용
p-coding.tistory.com
1. 괄호 문자 저장
먼저 StringTokenizer를 통해 소괄호, 대괄호를 기준으로 문자를 나눈다.
그렇게 되면 구분자를 저장하는 StringTokenizer의 특성을 활용해 문자를 가져올 수 있다.
true로 설정하면 구분자도 Token에 포함된다.
stringTokenizer = new StringTokenizer(sentence,"([)]",true);
2. 괄호 문자 찾아 균형확인하기
1. 구분자에 포함된 토큰 중에 괄호를 찾는다.
2. (, [ 라면 스택에 넣는다
3 - 1. ], ) 라면 스택에서 꺼내 비교한다
3 - 2. 이 때, 동일한 모양의 괄호 즉, )일 때 ( 괄호가 나오지 않는다면 균형이 맞지 않는 문자열로 처리
while(stringTokenizer.hasMoreTokens()) {
String token = stringTokenizer.nextToken();
if (token.equals("(") || token.equals("[")) {
push(token);
}
else if (token.equals(")")) {
if (!pop().equals("(")) {
isPerfect = false;
break;
}
}
else if (token.equals("]")) {
if (!pop().equals("[")) {
isPerfect = false;
break;
}
}
}
3. 스택에 남아있는 값 확인
마지막으로 스택에 남아 있는 경우 즉, (() 와 같은 문자열이 들어온다면 ( 이 스택에 남아 균형이 맞지 않는다.
if (!delimStack.isEmpty()) isPerfect = false;
스택을 활용하여 푸는 문제로 괄호를 저장하고 저장한 값을 꺼내 올 때,
다양한 경우에 대비하여 반론이 없게 푸는 것이 중요하다.
이번 문제는 빠르게 풀 수도 있지만, charAt함수가 아닌 StringTokenizer를 사용하듯이
다양한 방법으로 풀어보는 것을 추천한다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
private static LinkedList<String> delimStack;
private static void push(String delim){
delimStack.addLast(delim);
}
private static String pop(){
return delimStack.isEmpty() ? " " : delimStack.removeLast();
}
public static void main(String[] args) throws IOException {
delimStack = new LinkedList<>();
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder stringBuilder = new StringBuilder();
boolean isPerfect;
StringTokenizer stringTokenizer;
while (true) {
isPerfect = true;
delimStack.clear();
String sentence = bufferedReader.readLine();
if(sentence.equals(".")) break;
stringTokenizer = new StringTokenizer(sentence,"([)]",true);
while(stringTokenizer.hasMoreTokens()) {
String token = stringTokenizer.nextToken();
if (token.equals("(") || token.equals("[")) {
push(token);
}
else if (token.equals(")")) {
if (!pop().equals("(")) {
isPerfect = false;
break;
}
}
else if (token.equals("]")) {
if (!pop().equals("[")) {
isPerfect = false;
break;
}
}
}
if (!delimStack.isEmpty()) isPerfect = false;
stringBuilder.append(isPerfect ? "yes\n" : "no\n");
}
System.out.println(stringBuilder);
}
}
