[C++] 올바른 괄호

📄문제

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

 

⬇️ 입력

첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

(()(()))(()

()()(()())

 

⬆️ 출력

첫 번째 줄에 YES, NO를 출력한다.

NO

YES

 

📝 풀이

#include <iostream>
#include <cstring>

int main()
{
	char input[31];
	scanf_s("%s", input, sizeof(input));

	int left = 0, right = 0;
	int inputLen = strlen(input);

	// 괄호의 개수가 홀수라면?
	if (inputLen % 2 == 1)
	{
		printf("NO");
		return 0;
	}

	// 괄호의 양 끝이 잘못되었다면?
	if (input[0] == ')' || input[inputLen - 1] == '(')
	{
		printf("NO");
		return 0;
	}

	for (int i = 0; input[i] != '\0'; ++i)
		if (input[i] == '(')
			++left;
		else if (input[i] == ')')
			++right;

	printf("%s", left == right ? "YES" : "NO");
}

• 조건을 나누어 계산하였습니다. 열고 닫는 기준으로 괄호의 개수가 홀수개라면 잘못된것이기에 먼저 리턴하도록 하였습니다.
• 두번째 조건으로 양 끝쪽의 모양이 잘못되었다면, 이것도 닫히거나, 열린것이 아니기에 리턴합니다.
• 마지막으로 여는 개수와, 닫는 모양의 개수가 같으면 YES, 다르면 NO로 출력하여 마무리하였습니다.

 

#include <iostream>
#include <stack>

using namespace std;
int main()
{
	char str[31];
	scanf_s("%s", &str, sizeof(str));
	stack<bool> stack;

	for (int i = 0; i < str[i] != '\0'; ++i)
	{
		bool isOpen = str[i] == '(';

		if (!stack.empty() && stack.top() && !isOpen)
		{
			stack.pop();
			continue;
		}

		stack.push(isOpen);
	}

	printf("%s", stack.size() > 0 ? "NO" : "YES");
}

• stack 자료구조를 활용하면 더욱 쉽고 효율적으로 해결할 수 있습니다.
• stack에서 top이 열린 상태이고, 들어갈 괄호가 닫히는 괄호라면, pop을 통해 가장 위에 있는 괄호를 제거할 수 있습니다.
• 모든 괄호를 검사한 후 스택의 사이즈가 0보다 크다면, 닫히지 않은 괄호로 볼 수 있습니다.