[C] 백준 | 9012번 코드 - 괄호

>문제

> 핵심

스택

>풀이과정

어제 풀었던 4949번 문제랑 거~~의 똑같다.

어제 코드 조금만 고쳐서 냈다.

 

'(' 가 입력으로 들어오면 스택에 push

')' 가 입력으로 들어오면 스택에서 pop. 이때 pop된 값이 반드시 '(' 이어야 짝이 맞음.

짝이 안맞는 경우 chk=0 후 break.

 

문자열을 다 돌고 나왔을때, 스택이 비어있지 않거나, chk = 0 인 경우 -> 짝이 안맞으므로 NO. 이외는 YES.

 

위 과정을 N번 반복!..

 

 

인데 이대로 끝내기 아쉬워서 다른 방법을 사용한 코드도 한번 짜봤다.

 

chk = 1, cnt = 0에서 시작해서

'('가 입력으로 들어오면 cnt+=1;

')'가 입력으로 들어오면 cnt-=1;.  <- 이때, cnt<0 이 된다면 짝이 맞지않는다는 의미이므로 chk=0 이후 break;

 

반복문을 다 돌고 나왔을 때, cnt != 0 이거나, chk = 0 이라면, 짝이 맞지 않는다는 의미이므로 -> NO

이외에는 YES!

 

크게 어려운 로직은 아니다.

 

>깨달은점

스택은 어려웡

>코드

· 스택을 이용한 방법

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

#define SIZE 52

typedef struct
{
	char stack[SIZE];
	int n;
}StackType;

void init_stack(StackType* s)
{
	s->n = -1;
}

int is_full(StackType* s)
{
	return s->n == SIZE - 1;
}

int is_empty(StackType* s)
{
	return s->n == -1;
}

void push(StackType* s, char e)
{
	if (is_full(s))
		return;

	s->stack[++s->n] = e;
}

char pop(StackType* s)
{
	if (is_empty(s))
		return '!';

	char tmp = s->stack[s->n--];
	return tmp;
}

int main()
{
	StackType s;
	init_stack(&s);

	char text[SIZE], e;
	int i, j, n, chk = 1;

	scanf("%d", &n);
	getchar();

	for (i = 0; i < n; i++)
	{
		fgets(text, sizeof(text), stdin);

		for (j = 0; j < strlen(text) - 1; j++)
		{
			if (text[j] == '(')
				push(&s, text[j]);
			else if (text[j] == ')')
			{
				e = pop(&s);
				if (e != '(')
				{
					chk = 0;
					break;
				}
			}
		}
		if (!is_empty(&s))
			chk = 0;

		if (chk == 0)
			printf("NO\n");
		else
			printf("YES\n");

		chk = 1;
		s.n = -1;
	}

	return 0;
}

 

· 괄호 개수를 이용한 방법

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

#define SIZE 52

int main()
{
	char text[SIZE], e;
	int i, j, n, cnt = 0, chk = 1;

	scanf("%d", &n);
	getchar();

	for (i = 0; i < n; i++)
	{
		fgets(text, sizeof(text), stdin);

		for (j = 0; j < strlen(text) - 1; j++)
		{
			if (text[j] == '(')
				cnt += 1;
			else if (text[j] == ')')
			{
				cnt -= 1;
				if (cnt < 0)
				{
					chk = 0;
					break;
				}
			}
		}

		if (cnt!=0 || chk == 0)
			printf("NO\n");
		else
			printf("YES\n");

		cnt = 0; chk = 1;
	}

	return 0;
}