9012번: 괄호(BOJ C/C++)

9012번: 괄호(BOJ C/C++)

사용 언어: C

문제

괄호 문자열(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 <string.h>

int main(void)
{
	int T;
	scanf("%d",&T);
	char arr[50];
	for(int i=0;i<T;i++)
	{
		int left=0, right=0;
		scanf("%s",arr);
		int len=strlen(arr);
		for(int j=0;j<len;j++)
		{
			if(arr[j]=='(')
				left++;
			if(arr[j]==')')
				right++;
			if(right>left) 
			{
				printf("NO\n");
				break;
			}
		}
		if(right==left)
			printf("YES\n");
		else if(left>right)
			printf("NO\n");
	}
	return 0;
}

문제를 똑바로 읽지 않아서 '('와')'의 수만 같아도 되는 줄 알고 if(right>left): print(NO) 조건을 안 넣었어서 틀렸었다.

문제를 꼼꼼히 읽는 습관을 기르자.. 

 

두 번째 풀이

사실 이 문제는 스택으로 풀려 했지만 먼저 생각난 게 첫 번째 풀이(arr로 풀기)여서 일단 저 풀이로 풀었다.

 

문제를 풀기에 앞서 풀이 규칙을 세우자.

1. '(' 를 입력하면 스택에 push.

2. ')' 를 입력하면 스택에서 pop. 

   pop할때 top에 있는 문자 검사 -> '('가 아니면 성립이 안됨 -> NO

3. '(' 가 스택에 남아있는 상황, 즉 empty() 함수가 !=1 이면 -> NO 

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

#define MAX 52

typedef struct Stack{
	char arr[MAX];
	int top;
}Stack;

void init_stack(Stack* stack) //스택 초기화: top=-1
{
	stack->top=-1;
}

int full(Stack* stack)
{
	return (stack->top+1) == MAX;
}

int empty(Stack* stack)
{
	return (stack->top)==-1;
}

void push(Stack* stack, char cha)
{
	if (full(stack)) //꽉차면 더 이상 push하지 않음
		return;

	/*
	stack->top++;
	stack->arr[stack->top]=num;
	*/ //또 하나의 코드 줄이기 모먼트 발견
	
	stack->arr[++stack->top] = cha;
}

char pop(Stack* stack)
{
	if (empty(stack))
		return -1;
	
	/*
	char popcha = stack->arr[stack->top];
	stack->top--;
	*/
	
	char popcha = stack->arr[stack->top--]; 
	return popcha;
}

int main()
{
	Stack stack;

	char text[MAX], checkcha;
	int n;
	scanf("%d", &n);
	
	for(int i=0;i<n;i++)
	{
		init_stack(&stack); //for문 반복마다 stack 초기화
		int yesorno=1;      //for문 반복마다 YES, NO를 결정할 변수 초기화
		scanf("%s",text);
		for(int j=0;j<strlen(text);j++)
		{
			if(text[j]=='(')
				push(&stack, text[j]); //'(' 마다 stack에 push
			else if(text[j]==')')
			{
				checkcha = pop(&stack); //')'가 입력되면 top에 있는 문자 확인.
				if(checkcha != '(')     //'('가 아니면, 성립이 안되서 yesorno가 NO 값인 0이 된다. 
				{
					yesorno=0;
					break;
				}
			}
		}
		if(!empty(&stack)) //스택이 비어있지 않다는건, '('가 남아있는 상황이라는 것이므로 yesorno가 NO 값인 0이 된다.
			yesorno=0;
		if(yesorno==0)
			printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}

 

느낀 점

또 주석 처리를 한 /* ~ */ 부분에 이전에 쓰던 표현보다 코드를 더 단순하게 쓸 수 있는 표현을 찾았다.

//내 코드
stack->top++;
stack->arr[stack->top]=num;

//바뀐 코드
stack->arr[++stack->top] = cha;

//내 코드
char popcha = stack->arr[stack->top];
stack->top--;

//바뀐 코드
char popcha = stack->arr[stack->top--];

사실 내가 쓰는 코드가 더 직관적으로 해석할 수 있는 면이 있긴 하지만, 더 단순한 표현들에 아직 매료되어있는 것 같다. 

 

구조체 스택을 한번 구현하고 공부해보니 구조체 스택으로 표현하는 것도 그렇게 어렵진 않다는 생각이 든다.

(https://sedangdang.tistory.com/22를 좀 참조한건 안 비밀...)

열심히 살자...!!