[Baekjoon/백준] 9012번: 괄호(C/C++)

단계별로 풀어보기 18단계(스택) 3번 문제

이번 문제는 학교 과제로 이미 한번 풀어봤던 문제다. 그래서 이번 문제는 코드 주석으로 설명이 적혀있어, 따로 접근 방법과 풀이가 없다.

https://www.acmicpc.net/step/11

스택 단계

---

백준 9012번: 괄호

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

9012번: 괄호

---

문제 설명

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

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

---

입력과 출력

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

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

---

코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 50		//스택 최대크기 50

typedef char element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;	//스택 구조체로 정의

void init_stack(StackType *s) {	//스택 초기화 함수
	s->top = -1;
}

int is_empty(StackType *s) {	//스택 공백 상태 검출 함수
	return (s->top == -1);	//top 값이 -1이라면 true(1) 반환, 아니라면 false(0) 반환
}

int is_full(StackType *s) {	//스택 포화 상태 검출 함수
	return (s->top == (MAX_STACK_SIZE-1));
}

void push(StackType *s, element item) { //스택을 추가하는 함수
	if (is_full(s)) 		 	 //만약 스택이 최대치라면
		return;			//함수 종료
	else s->data[++(s->top)] = item;		//최대치가 아니라면 data[top+1]에 항목 저장
}

element pop(StackType *s) {	//스택 제거 함수
	if (is_empty(s))		//만약 스택이 공백 상태라면
		return;		//함수 종료
	else return s->data[(s->top)--];	//공백이 아니라면 스택 최대치 값(top) 1 감소
}

int check_matching(const char *in)	//괄호 문자열 검사 함수(반환 값이 1이면 VPS, 0이면 VPS 아님)
{
	StackType s;		//구조체 s 선언
	char ch, open_ch;	//괄호 문자열에 사용한 변수들 선언
	int n = strlen(in);	//strlen은 문자열 길이를 세는 함수
	init_stack(&s);		//스택 값(top) 초기화(top = -1)

	for (int i = 0; i < n; i++) { //n(괄호 문자열(in)의 길이와 같은 값)까지 반복
		ch = in[i];	//ch를 입력받은 괄호 문자열의 i번 인덱스로 지정
		switch (ch) {
		case '(':			//ch가 ’(’인 경우
			push(&s, ch);	//스택을 추가하고
			break;		//이후 생략
		case ')':					//ch가 ‘)’인 경우
			if (is_empty(&s)) return 0;	//만약 스택이 공백이라면 0을 반환
			else {				//아니라면
				open_ch = pop(&s);	//open_ch에 스택 최곳값을 제거한 값을 넣고
				break;			//이후 생략
			}
		}
	}
	if (!is_empty(&s)) return 0;	//스택이 공백 상태가 아니라면 0을 반환
	return 1;		//공백 상태라면 1을 반환
}

int main(void)
{
	char *p = (char *)malloc(sizeof(char) * MAX_STACK_SIZE); //괄호를 받을 동적 할당 문자열
	int T;		//몇 개의 괄호 문자열을 받을지 입력할 정수
	scanf("%d", &T);	//T의 정수값을 입력받아 저장

	for (int i = 0; i < T; i++)	//T값까지 반복
	{
		scanf("%s", p);			//괄호 문자열을 입력받아 p에 저장
		if (check_matching(p) == 1)	//만약 괄호 문자열 검사 결과 1(VPS, 올바른 괄호)라면
			printf("YES\n");		//YES를 출력
		else				//VPS가 아니라면
			printf("NO\n");		//NO를 출력
	}

	free(p);		//동적 할당 메모리 반환
	return 0;
}

---

결과

백준 제출 결과