백준 c++ 9012 문제 풀이

문제 링크 : https://www.acmicpc.net/problem/9012

목차

1. 설명

 

2. 내 코드

 

3. 문제 풀이 해석 내용

 

4. 실행 결과

 

설명

백준 실버 4 문제 입니다.

문제명 : 괄호

 

내 코드

#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
    
    int n;
	cin >> n;

	while (n--)
	{
		string input;
		cin >> input;

		stack<char> stack;
		bool isTrue = false;

		if (input.length() % 2 != 0)
		{
			cout << "NO" << endl;
			continue;
		}

		for (int i = 0; i < input.length(); ++i)
		{
			if (input[i] == '(')
			{
				stack.push(1);
			}
			else
			{
				if (stack.size() > 0)
				{
					stack.pop();
				}
				else
				{
					isTrue = true;
				}
			}
		}

		if (!stack.empty() || isTrue)
		{
			cout << "NO" << endl;
		}
		else
		{
			cout << "YES" << endl;
		}
	}
}

 

문제 풀이 해석 내용

 

문자열 처리 루프

while (n--)
{
    // ... (내부 코드) ...
}

while (n--): n번 반복하는 루프입니다. 

각 반복은 하나의 괄호 문자열을 처리합니다.

 

 

각 문자열 내부

string input;
cin >> input;

stack<char> stack;
bool isTrue = false;

string input; cin >> input;: 현재 테스트 케이스의 괄호 문자열을 input 변수에 입력받습니다.
stack<char> stack;: 괄호 짝을 맞추기 위한 스택(std::stack)을 선언합니다. 

여기서는 char 타입(문자)을 저장하지만, 실제로는 괄호 존재 여부만 확인하므로 어떤 타입이든 상관없습니다.
bool isTrue = false;: 괄호 짝이 맞지 않는 상황(예: 닫는 괄호가 나왔는데 스택이 비어있는 경우)이 발생했는지 기록하는 플래그 변수입니다. 초기값은 false입니다.

 

 

문자열 길이 검사

if (input.length() % 2 != 0)
{
    cout << "NO" << endl;
    continue;
}

input.length(): 문자열의 길이를 반환합니다.
input.length() % 2 != 0: 문자열의 길이가 홀수인지 확인합니다. 

올바르게 짝지어진 괄호 문자열은 항상 짝수 길이입니다.
만약 길이가 홀수이면 즉시 "NO"를 출력하고 continue를 사용하여 현재 루프의 남은 부분을 건너뛰고 다음 문자열 처리로 넘어갑니다.

 

 

괄호 유효성 검사

for (int i = 0; i < input.length(); ++i)
{
    if (input[i] == '(')
    {
        stack.push(1); // 여는 괄호가 나오면 스택에 추가
    }
    else // 닫는 괄호인 경우 ')'
    {
        if (stack.size() > 0)
        {
            stack.pop(); // 스택에 여는 괄호가 있으면 짝을 맞춰 pop
        }
        else
        {
            isTrue = true; // 스택이 비어있는데 닫는 괄호가 나오면 유효하지 않음
        }
    }
}

for 루프를 사용하여 문자열 input의 각 문자를 순서대로 검사합니다.
if (input[i] == '('): 현재 문자가 여는 괄호이면
stack.push(1);: 스택에 임의의 값(여기서는 1)을 푸시합니다. 

스택에 여는 괄호가 있다는 것을 표시합니다.
else: 현재 문자가 닫는 괄호 ')'이면

if (stack.size() > 0): 스택이 비어있지 않으면 (즉, 짝을 맞출 여는 괄호가 있으면)
stack.pop();: 스택에서 가장 위에 있는 요소를 제거합니다. 여는 괄호와 닫는 괄호가 짝을 맞췄다는 의미입니다.
else: 스택이 비어있으면 (닫는 괄호가 나왔는데 짝을 맞출 여는 괄호가 없는 경우)
isTrue = true;: isTrue 플래그를 true로 설정합니다. 이는 잘못된 괄호 조합이 발생했음을 나타냅니다.

 

 

최종 유효성 판단 및 출력

if (!stack.empty() || isTrue)
{
    cout << "NO" << endl;
}
else
{
    cout << "YES" << endl;
}

if (!stack.empty() || isTrue): 문자열 전체를 검사한 후, 다음 두 가지 경우 중 하나에 해당하면 "NO"를 출력합니다.
!stack.empty(): 스택이 비어있지 않으면 (즉, 모든 닫는 괄호가 처리된 후에도 짝을 맞추지 못한 여는 괄호가 남아있으면).
isTrue: 검사 도중 닫는 괄호가 나왔는데 짝을 맞출 여는 괄호가 없었던 경우.
위 조건에 해당하지 않으면 (스택이 비어있고 isTrue가 false이면), 모든 괄호가 올바르게 짝지어졌다고 판단하여 "YES"를 출력합니다.

 

 

실행 결과