https://www.acmicpc.net/problem/9012
스택을 이용하면 쉽게 풀 수 있는 문제였습니다. 하지만 저는 문자열을 입력 받는 방법이 잘못되어 오랜 시간 어려움을 겪었습니다. 기본의 중요성을 다시 한번 깨닫는 계기가 되었습니다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 51
#define boolean unsigned char
#define true 1
#define false 0typedef char Element;
Element stack[MAX_SIZE];
int top = -1;//)(() = NO
void push (Element e){
stack[++top] = e;
}Element peek(){
return stack[top];
}Element pop(){
return stack[top--];
}
우선 기본적으로 stack 기본 함수인 push, peek, pop을 구현하였습니다. 각 함수의 구체적인 역할을 설명하자면 push는 Element e를 스택에 쌓는 역할, peek은 스택의 top에 위치한 요소를 그래도 둔 채 확인만 하는 역할, pop은 스택의 top에 위치한 요소를 빼내는 역할을 합니다.
int main(int argc, char *argv[]) {
int n;
scanf("%d",&n);
fflush(stdin);
int i;
for( i=0; i<n; i++){
//scanf("%[^\n]\n",s);
//fgets(tmp,sizeof(tmp),stdin);
top=-1;
char tmp[51];
scanf("%s", tmp);
fflush(stdin); 입력을 받을 횟수 n 그리고 각 문자열을 scanf로 입력 받았습니다.
//scanf(“%[^\n]\n”,s);
//fgets(tmp,sizeof(tmp),stdin);
위와 같이 문자열을 입력 받는 방식도 있다고 알고 있었는데 학습이 필요할 것 같습니다. 저는 이 부분을 착각하여 오랜 시간 문제가 풀리지 않았었습니다. 독자 여러분들 중에는 정확한 차이를 아시는 분들이 많을 것이라 생각합니다.
int j = 0;
while(tmp[j]=='(' || tmp[j]==')'){
if(j==0 || top==-1 ){
push(tmp[j]);
} else if ( peek()=='(' && tmp[j]==')' ) {
pop();
}else {
push(tmp[j]);
}
j++;
}
if(top!=-1){
printf("NO\n");
} else {
printf("YES\n");
}
}
return 0;
}
이번 문제의 핵심 부분입니다.
1. 처음으로 문자열을 탐색하거나 (j==0) 스택이 쌓여있지 않은 경우 (top == -1 )에는 무조건 push를 합니다.
2. 스택의 최상단 요소가 ‘(’ 이고 문자열의 요소가 ‘)’ 라면 pop을 합니다. 개인적으로 이 부분이 문제풀이의 핵심이라고 생각합니다.
3. 위와 같은 경우들이 아니라면 push합니다.
j++를 해가면서 모든 문자열을 탐색합니다. 그리고 마지막으로 스택을 확인하여 스택에 무언가 남아있다면 (top!=-1) NO를 출력하고 아니라면 YES를 출력합니다. 스택에 아무것도 남지 않았다는 것은 괄호의 짝이 잘 맞았다는 것을 의미합니다. 추가적으로 )((( 와 같이 ‘)’ 닫는 괄호가 먼저 나오는 경우를 고려하여야 문제가 풀립니다.
