백준 4949번 C언어

백준 9012번과 유사하면서 더 어려운 문제이다. 

문자열을 입력받는 과정에서 많이 애를 먹었는데 처음 생각한것은 문자열 배열 하나만을 입력받고

배열의 길이만큼 하나씩 검사하는 방향으로 잡았는데 잘 안풀렸다..!

 

루프를 돌리면서 문자열 배열을 계속 입력받고, 그 배열을 검사하는 식으로 구현을 바꿨더니 풀렸다. 

 

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

4949번: 균형잡힌 세상

 

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

---

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

---

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

---

 

해결방안 -> while문을 돌리면서 문자열 배열을 입력받는다 (이떄 스택도 초기화를 해준다). 배열의 길이만큼 for문을 

돌리면서 만약 배열의 값이 '(' ')' '[' ']' 일떄에 대하여 검사를 한다. 

스택의 topindex값과 배열의 값을 비교해서 만약 배열의 값이 ) 이고 스택의 topindex값이 ( 이면 Pop연산을 한다.

마찬가지로 스택의 topindex값이 [ 이고 배열의 값이 ] 이면 Pop연산을 한다.

그 외에는 Push연산을 한다.

for문이 끝났을때 배열이 비어있다면 균형을 이루고 있으므로 yes를 출력하고 배열이 비어있지 않다면 no를 출력한다.

 

전체 소스 코드

 

#include <stdio.h>

#include <string.h>

#define True 1

#define False 0

typedef struct _stack{

    char arr[101];

    int topindex;

}stack; //스택 구조체 정의

 

typedef stack Stack;

 

void Stackinit(Stack *pstack){ //스택의 초기화를 담당하는 함수

    pstack->topindex = -1;

}

 

int Empty(Stack *pstack){ //스택이 비어있는지 검사하는 함수

    if(pstack->topindex == -1){

        return True;

    }

    else

        return False;

}

 

char return_top(Stack *pstack){ //스택의 가장 위에 있는 topindex 값을 반환시킨다.

    return pstack->arr[pstack->topindex];

}

 

void Push(Stack *pstack,char data){ //스택의 Push연산

 

    pstack->topindex = pstack->topindex + 1;

    pstack->arr[pstack->topindex] = data;

 

}

 

void Pop(Stack *pstack){ //스택의 Pop연산

    pstack->topindex = pstack->topindex - 1;

}

 

int main(void){

 

 

    Stack stack;

    Stackinit(&stack); //스택의 생성과 초기화

 

    while(True){   //while문을 돌리면서 문자열 배열을 입력받는다.

        char arr[100];  //길이가 100인 문자열 배열

          gets(arr);

        Stackinit(&stack);  //반복문을 돌리면서 스택의 초기화도 해준다.

        if(strcmp(arr,".") == 0)  //문자열의 끝이 "."이므로 break문을 통해 탈출

            break;

        for(int i = 0;i<strlen(arr);i++){  //문자열 배열의 요소 검사하는 For문

            if(arr[i] == '(' || arr[i] == ')' || arr[i] == '[' || arr[i] == ']'){  //배열의 값이 ( ) [ ] 일떄

 

 

                  if(arr[i] == ')' && return_top(&stack) == '('){

//topindex값이 (이고 배열의 값이 ) 이면 짝을 이뤄서 Pop연산

                      Pop(&stack);  

                  }

                  else if(arr[i] == ']' && return_top(&stack) == '['){ 

//마찬가지로 topindex값이 [ 이고 배열의 값이 ]이면 짝을 이뤄서 Pop 연산                       

                      Pop(&stack);

                  }

                  else{

                      Push(&stack,arr[i]);    //그외에는 Push연산을 한다.

                  }

 

 

            }

    }

 

         if(Empty(&stack)){

            printf("yes\n");  //for문이 끝나고 스택이 비어있는 경우(균형을 이룬 경우)에 yes출력

        }

        else{

            printf("no\n");  //그외에는 no 출력

        }

 

}