[백준 / C언어] Day7. 균형잡힌 세상 (4949)

2024. 05. 24 - 코딩테스트 스터디 Day7

일단 시원하게 울고 시작한다

 

아무리 봐도 코드가 맞는 것 같은데 자꾸 출력 초과가 떠서 정답 판정받을 때까지 정말 오랜 시간이 걸렸다... ㅎㅎ

 

 

 

01. 문제

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

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

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

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

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

 

 

02. 입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

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

 

 

03. 출력

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

 

 

04-1. 예제 입력 1

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

 

 

04-2. 예제 출력 1

yes
yes
no
no
no
yes
yes

 

 

05. 힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형 잡힌 문자열로 간주할 수 있다.

 

 

06. 풀이 및 답

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 102

int main() {
    char stack[MAX_SIZE];
    char str[MAX_SIZE]; // 문자열 입력받을 공간
    
    while (1) {
        fgets(str, MAX_SIZE, stdin);
        if (str[0] == '.' && str[1] == '\n') break;
        str[strcspn(str, "\n")] = 0;
        
        int top = -1;
        int check = 1; // 괄호 짝이 맞는지 표시, 짝이 맞으면 1
        
        for (int i = 0; str[i] != '\0'; i++) {
            if ( str[i] == '.' ) break;
            
            /* 왼쪽 괄호 -> 스택에 추가 */
            if ( str[i] == '(' || str[i] == '[' ) {
                stack[++top] = str[i];
            }
            
            /* 오른쪽 소괄호 */
            else if ( str[i] == ')' ) {
                
                /* (1)스택이 비어있거나 스택의 탑이 왼쪽 소괄호가 아닐 때 */
                if (top == -1 || stack[top] != '(') {
                    check = 0; // 괄호 짝이 맞지 않음
                    break;
                }
                
                /* (2)스택이 비어있지 않고, 스택의 탑이 왼쪽 소괄호일 때 (즉, 짝이 맞을 때) */
                else {
                    --top; // 스택에서 제거 (상쇄)
                }
            }
            
            /* 오른쪽 대괄호 */
            else if ( str[i] == ']' ) {
                
                /* (1)스택이 비어있거나 스택의 탑이 왼쪽 대괄호가 아닐 때 */
                if (top == -1 || stack[top] != '[') {
                    check = 0; // 괄호 짝이 맞지 않음
                    break;
                }
                
                /* (2)스택이 비어있지 않고, 스택의 탑이 왼쪽 대괄호일 때 (즉, 짝이 맞을 때) */
                else {
                    --top; // 스택에서 제거 (상쇄)
                }
            }
        }
        
        /* 스택이 비어있지 않고, check가 0인 경우 (즉, 모든 괄호의 짝이 맞지 않는 경우) */ 
        if (top != -1 || check == 0) {
            printf("no\n");
        } else {
            printf("yes\n");
        }
    }
    return 0;
}

우선 이번 문제도 스택을 사용하여 풀이하였다.

문자열을 입력받을 공간을 str, 괄호의 짝이 맞는지 확인하기 위한 스택은 stack으로 선언해 줬다.

 

우선 온점 하나 '.'를 입력받기 전까지 무한루프를 돌도록 만들었다.

문자열을 입력받을 때는 fgets()을 사용하였다. scanf()는 개행 문자(\n), 공백 문자, 탭 문자까지만 하나의 문자열로 보기 때문에 이 문제처럼 공백 문자가 포함되어 있는 문자열을 입력받는 경우에는 사용하지 않는 것이 좋다고 한다. 또한 gets() 함수는 보안상의 문제가 있다고 하니 fgets()를 사용하는 것이 좋은 것 같다.

str 문자열의 개행문자 '\n'을 '\0'로 바꿔주어 개행문자 뒤의 문자들을 다 날려버려 처리를 편하게 할 수 있도록 만든다.

 

top은 스택의 최상위를 가리키는 인덱스이며 -1이면 스택이 비어있다는 뜻이다.

check는 괄호의 짝이 맞는지를 표시하기 위해 선언한 변수이다. 

이 두 변수는 각 문자열마다 새로운 값을 가져야 하기 때문에 while문 안에서 초기화하도록 해준다.

 

문자열에 있는 '\0'을 만날 때까지(즉, 문자열이 끝날 때까지) for문을 돌면서 괄호의 짝이 맞는지 확인한다. 문제에서 요구한 대로 '.'를 만나면 반복문을 빠져나가도록 코드를 작성했다.

 

문자열 내부에서 왼쪽 소괄호 '('나 왼쪽 대괄호 '['를 만나면, 스택에 push 한다.

 

문자열 내부에서 오른쪽 소괄호 ')'를 만나면, 

    - 스택이 비어있거나 스택의 탑이 왼쪽 소괄호 '('가 아닌 경우, 괄호의 짝이 맞지 않다는 소리이므로 check 값을 0으로 바꿔주고, 반복문을 빠져나간다.

    - 스택이 비어있지 않고, 스택의 탑이 왼쪽 소괄호 '('인 경우, 괄호의 짝이 맞는다는 소리이므로 스택에서 제거한다.

오른쪽 대괄호']'의 경우도 마찬가지이다.

 

for문을 빠져나온 뒤엔 스택이 비어있지 않거나 check가 0인 경우에는 "no"를 출력하고, 그렇지 않은 경우에는 "yes"를 출력하도록 한다.

 

정답!!

 

 

 

---

 

다 풀고 나서 이것저것 건드려보며 알아낸 결과... 출력 초과가 계속 떴던 이유는 문자열의 MAX_SIZE를 잘못 설정해 줬기 때문이다.

문제에서 문자열의 최대 크기가 100이라고 명시해 줬기 때문에 아무 생각 없이 101로 설정해 줬다. 

(문자열 최대 크기(100) + 널 문자 크기(1) = 101)

 

그런데 여기서 문제는 fgets 함수는 [MAX_SIZE-1]만큼의 공간을 필요로 한다.

[MAX_SIZE-1]는 문자열 최대 크기에 '\0'의 크기까지 포함한 것이다.

따라서 MAX_SIZE는 문자열 최대 크기 + 2이다. (문자열의 크기 + 개행문자(\n) + 문자열의 끝(\0))

 

이게 무슨 소리냐면, 만약 fgets 함수에 사이즈로 5를 전달하면, 5만큼 문자열을 채우고 그 뒤에 널 문자를 덧붙이는 것이 아니라 주어진 5칸 안에 널 문자까지 들어갈 수 있도록 문자열을 4만큼 채운다.

우리는 문자열이 최대 100글자까지 입력되도록 해야 하고, 여기에 개행 문자와 널 문자까지 모두 입력받을 수 있도록 사이즈를 2만큼 추가하여 102로 지정해줘야 하는 것이다.

 

예)

"Hello"라는 문자열을 fgets 함수로 입력한다.

그렇다면 나는 "Hello" 문자열에 엔터(\n)를 입력할 것이고, fgets 함수는 이걸 받아서 맨 뒤에 널 문자 \0를 붙여 "APPLE\n\0"로 저장을 하게 될 것이다.

 

 

---

여러 게시물의 도움을 받았다.

풀이하는 과정은 정말 힘들었지만... 나중에 큰 도움이 될 것이라고 생각한다. ㅎ.ㅎ

 

https://sedangdang.tistory.com/21

[C] 백준 | 4949번 코드 - 균형잡힌 세상

https://www.ibm.com/docs/ko/i/7.3?topic=functions-fgets-read-string

fgets() — 스트링 읽기

https://www.acmicpc.net/board/view/128169