[C언어] 백준 4949 : 균형잡힌 세상

백준 4949 : 균형잡힌 세상

 

문제 링크

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

 

문제 내용

(요약) "(" 와 ")", "[" 와 "]"이 서로 짝을 이루면 균형잡힌 문자열이라고 할 때,

주어진 문자열에 대해 균형잡힌 문자열인지 아닌지를 판단하자.

 

 

Idea

(, ), [, ] 를 만날 때마다 스택에 push하거나 pop하면서 균형잡힌 문자열인지 판단한다.

1. "(" 또는 "["를 만나면 스택에 쌓는다.
2. ")" 또는 "]"를 만나면 스택의 상단 부분 데이터와 비교하여 서로 짝을 이룬다면 pop해준다.
3. 짝을 이루지 않는다면 push한다.

 

스택의 인덱스를 가리키는 top가 -1 이라면 스택에 데이터가 없다는 뜻이므로 균형잡힌 문자열이다.

스택에 대한 설명은 여기로.

 

 

Code

#include <stdio.h>
#include <string.h>
#define MAX 100
 
char stack[MAX];
int top = -1;
 
//스택에 데이터를 집어넣는다.
int push(char ch) {
    if (top >= MAX - 1) return -1;
    return stack[++top] = ch;
}
 
//스택에서 데이터를 뽑는다.
int pop() {
    if (top < 0) return -1;
    return stack[top--] = '\0';
}
 
//스택 상단의 내용을 읽는다.
char peek() {
    return stack[top];
}
 
//균형잡힌 문자열인지를 판단
void Result(char *ch, int size) {
    for (int i = 0; i < size; i++) {
        if (ch[i] == '(' || ch[i] == ')' || ch[i] == '[' || ch[i] == ']') {
            //top가 -1이라면 무조건 push
            if (top == -1) push(ch[i]);
            else {
                //짝이라면 pop
                if (peek() == '('&&ch[i] == ')') pop();
                else if (peek() == '['&&ch[i] == ']') pop();
                //그 외 push
                else push(ch[i]);
            }
        }
    }
    //top가 -1이면 균형잡힌 문자열
    if (top == -1) printf("yes\n");
    else printf("no\n");
}
 
int main() {
    char str[MAX];
    while (1) {
        top = -1;
        gets(str);
        if (strcmp(str, ".") == 0) break;
        Result(str, strlen(str));
    }
    return 0;
}