[백준 / C언어] Day6. 괄호 (9012)

2024. 05. 23 - 코딩테스트 스터디 Day6

 

 

01. 문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’와 ‘)’ 만으로 구성되어 있는 문자열이다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO로 나타내어야 한다. 

 

 

02. 입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

 

 

03. 출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

 

04-1. 예제 입력 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

 

 

04-2. 예제 출력 1

NO
NO
YES
NO
YES
NO

 

 

05-1. 예제 입력 2

3
((
))
())(()

 

 

05-2. 예제 출력 2

NO
NO
NO

 

 

06. 풀이 및 답 - C언어

 

코드를 작성하기 전 VPS가 되기 위한 조건에 대해 생각해보고 시작하였다.

 

VPS가 되기 위한 조건은 다음과 같다.

1. '('와 ')'의 개수가 같다
2. ')'의 개수가 '('보다 더 먼저 많아지면 안된다

 

두 조건 모두를 만족시키기 위해서 '('와 ')'의 짝이 맞으면 상쇄되도록 코드를 짜기로 결심했다. 따라서 '('가 나오면 count를 +1 하고, ')'가 나오면 count를 -1 하도록 만든다.

이때, count가 -1이 되면 '('보다 ')'가 더 먼저 많이 나온 것이기 때문에 "NO"를 출력하도록 한다. 이러면 2번 조건을 만족시킬 수 있다.

문자열을 다 검사하고 났을 때, count가 0이면 양쪽 괄호의 개수가 같다는 뜻이므로 "YES"를 출력하도록 한다. 이러면 1번 조건을 만족시킬 수 있다.

 

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

int main() {
    int k, count; // 입력 데이터 수
    char str[50]; // 입력 괄호 데이터
    scanf("%d", &k);
    
    for (int i = 0; i < k; i++) {
        scanf("%s", str);
        count = 0;
        
        for (int j = 0; j < strlen(str); j++ ){
            if ( str[j] == '(' ) {
            count++;
            }
            else {
                count--;
            }
        
            if ( count < 0 ) {
                break;
            }
        }
        if ( count == 0 ) {
            printf("YES\n");
        } 
        else {
            printf("NO\n");
        }
    }
    return 0;
}

최종적으로 작성한 코드는 위와 같다.

 

우선 k를 입력받아 k만큼 반복문을 돌면서 입력 괄호 문자열을 입력받도록 한다.

입력받은 괄호 문자열 str의 길이만큼 반복문을 돌면서 str의 각 문자들이 '('인지, ')'인지에 따라 count 값에 1을 더하거나 빼준다. 이때, count 값이 0보다 작아지면, ')'의 수가 '('보다 더 먼저 많아졌다는 뜻이므로, 반복문을 빠져나간다.

문자열의 검사를 마친 뒤엔 count값이 0인 경우, 즉 '('과 ')'의 개수가 같으면서 ')'의 수가 '('보다 더 먼저 많아지지 않는 경우에 "YES"를 출력한다. 그렇지 않은 경우에는 "NO"를 출력한다.

 

count는 각 문자열마다 새로 판단해야 하므로 각 문자열 검사 전 초기화를 진행해야 한다는 점을 잊지 말아야 한다.

나는 이걸 미처 생각하지 못해서 좀 시간이 걸렸다. ㅎㅎ

 

또, 아무 생각 없이 풀다가 for문에서 조금 헤맸다.

문자열 하나하나의 요소를 살펴보기 위해서는 for문 내부에 for문을 하나 더 작성하여 사용해야 한다.

 

아무튼 정답!

 

---

스택으로 풀이한 분도 있길래 공부할 때 참고하려고 티스토리 주소를 남겨둔다. ^_^

 

https://yahohococo.tistory.com/31

[C] 백준 9012번: 괄호