[C] 백준 - 4949번: 균형잡힌 세상

4월 12일(수) - 스택 (4949번)

4949번: 균형잡힌 세상

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 직전 9012번 문제에서는 스택을 활용하지 않고도 풀이가 가능했었지만, 이번 문제는 스택을 활용해야할듯

- while(1) 안에서 gets로 입력을 받는다. 대신 "."가 입력되는 경우에는 break

- 그리고 이어지는 for문 안에서

  ( 혹은 [ 가 입력되는 경우에는 바로 push

  ) 혹은 ] 가 입력되는 경우에는, 만약 ( 혹은 [ 가 입력되어있다면 pop을 진행하고 / 아니면 break

- 위에서 사용한 조건들을 토대로, while(1)안에서 yes 혹은 no 출력하고 종료

 

int main(void)
{
	while (1)
	{
		gets(str);
		if (strcmp(str, ".") == 0)
		{
			break;
		}

		top = -1;
		int len = strlen(str);
		for (int i = 0; i < len; i++)
		{
			if (str[i] == '(' || str[i] == '[')
			{
				push(str[i]);
			}
			else if (str[i] == ')')
			{
				if (...)
				{
					pop();
				}
				else
				{
					...
					break;
				}
			}
			else if (str[i] == ']')
			{
				if (...)
				{
					pop();
				}
				else
				{
					...
					break;
				}
			}
			else
			{
				continue;
			}
		}

		if (...)
		{
			printf("yes\n");
		}
		else
		{
			printf("no\n");
		}
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

while (1)
	{
		gets(str);
		if (strcmp(str, ".") == 0)
		{
			break;
		}
		
       		top = -1;
		int check = 1;
		int len = strlen(str);
		for (int i = 0; i < len; i++)
		{
			if (str[i] == '(' || str[i] == '[')
			{
				push(str[i]);
			}
			else if (str[i] == ')')
			{
				if (top>-1 && stack[top] == '(')
				{
					pop();
				}
				else
				{
					check = 0;
					break;
				}
			}
			else if (str[i] == ']')
			{
				if (top>-1 && stack[top] == '[')
				{
					pop();
				}
				else
				{
					check = 0;
					break;
				}
			}
		}

		if (check == 1 && empty()==0)
		{
			printf("yes\n");
		}
		else
		{
			printf("no\n");
		}
		
	}

1. while문안에서 ) 혹은 ] 가 입력된 경우, pop을 하기 위한 조건이 너무 복잡해졌다

-> empty 함수라던가, check 변수까지 너무나도 다양한것들을 만들어서 오히려 헷갈리고, yes / no 출력조건도 꼬였다

-> 단순화

-> 풀이 - 1

 

// 풀이 - 1
void push(char x)
{
	stack[++top] = x;
}

void pop()
{
	top--;
}

// 풀이 - 2
int push(char input)
{
	if (top >= 101 - 1)
	{
		return -1;
	}
	top++;
	return stack[top] = input;
}

int pop()
{
	if (top < 0)
	{
		return -1;
	}
	return stack[top--] = '\0';
}

2. push와 pop 함수들을 구현하는 과정에서 return 조건을 void 혹은 int 둘 중 어느것으로 사용할지 혼돈스러웠다

-> main에서 어찌 활용하느냐에 따라서 달라진다

-> main함수 안에서의 활용을 끝까지 생각해본 이후에 정해야할듯

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int top = -1;
char stack[101], str[101]; 

void push(char x)
{
	stack[++top] = x;
}

void pop()
{
	top--;
}

int main(void)
{
	while (1)
	{
		gets(str);
		if (strcmp(str, ".") == 0)
		{
			break;
		}

		top = -1;
		int len = strlen(str);
		for (int i = 0; i < len; i++)
		{
			if (str[i] == '(' || str[i] == '[')
			{
				push(str[i]);
			}
			else if (str[i] == ')')
			{
				if (stack[top] == '(')
				{
					pop();
				}
				else
				{
					push(str[i]);
					break;
				}
			}
			else if (str[i] == ']')
			{
				if (stack[top] == '[')
				{
					pop();
				}
				else
				{
					push(str[i]);
					break;
				}
			}
			else
			{
				continue;
			}
		}

		if (top != -1)
		{
			printf("no\n");
		}
		else
		{
			printf("yes\n");
		}
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(내 풀이와는 약간 다른 방식, 나중에 복습할때 같이 참고할것 / 출처 -> https://wtg-study.tistory.com/16 )

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

char stack[101];
int top = -1;

int push(char input)
{
	if (top >= 101 - 1)
	{
		return -1;
	}
	top++;
	return stack[top] = input;
}

int pop()
{
	if (top < 0)
	{
		return -1;
	}
	return stack[top--] = '\0';
}

int main(void)
{
	char string[101];

	while (1)
	{
		top = -1;
		gets(string);
		if (strcmp(string, ".") == 0)
		{
			break;
		}

		int len = strlen(string);
		for (int i = 0; i < len; i++)
		{
			if (string[i] == '(' || string[i] == ')' || string[i] == '[' || string[i] == ']')
			{
				if (top == -1)
				{
					push(string[i]);
				}
				else
				{
					if (stack[top] == '(' && string[i] == ')')
					{
						pop();
					}
					else if (stack[top] == '[' && string[i] == ']')
					{
						pop();
					}
					else
					{
						push(string[i]);
					}
				}
			}
		}

		if (top == -1)
		{
			printf("yes\n");
		}
		else
		{
			printf("no\n");
		}
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ