백준 알고리즘에서 예제가 두개가 나온다면 대개 두번째 예제에서 키를 찾을 수 있다.
이 문제도 같은데,
1번 예제에서 파악할 수 있는것은 문제에 나와있는대로 VPS에 대한 룰이다.
여는 괄호인 '('와 닫는 괄호인 ')'가 쌍으로 나와야 VPS라는 간단한 룰이다.
하지만 2번 예제에서는 좀 더 자세하게 알려주는데
())(() -> NO
위와 같이 나와있다. 여는 괄호 3개 닫는 괄호 3개로 모두 쌍을 이루고 있지만,
중간에 닫는 괄호와 여는 괄호의 위치가 반대로 나와있다.
이는 즉 괄호의 쓰임새에 맞게 짝이 맞는 여는 괄호가 앞에 나온게 아니면 닫는 괄호는 못쓴다는 뜻이다.
예로들어 ((())()) 이와 같은 괄호 나열은 YES가 나온다는 것이다.
조금 더 쉽게 이해하기 위해 뜯어 보자면
( ( ( ) ) ( ) )
이런식이란 뜻이다. 형태를 보면
평소에 쓰던 코드 형식과 유사하다.
if(조건)
{
if(조건)
{
if(조건)
{
}
}
}
이러한 형태라는 것이다.
문제는 어떻게 구현할 것인가? 인데 이 역시 간단하다.
전등을 키고 끄는 스위치를 생각해보면 된다.
여는 괄호를 + 닫는 괄호를 -로 가정했을때
괄호를 한번 열때마다 count변수엔 +1이 되고
괄호를 한번 닫을때마다 count 변수엔 -1이 되는데
단, 0 미만이 될 경우 그 즉시 break를 한 후 NO를 띄워주면 된다.
그리고 모든 괄호의 수를 계산했을때 count변수가 0이면 딱 맞아 떨어진다는 뜻으로 YES를 띄워주면 된다.
이하는 코드
#include <iostream>
#include <string>
using namespace std;
int main()
{
int nInputIter = 0;
cin >> nInputIter;
cin.ignore();
string strInput{};
int nCount{};
bool bAns = true;
for (int i = 0; i < nInputIter; i++)
{
cin >> strInput;
for (int j = 0; j < strInput.length(); j++)
{
if (strInput[j] == '(')
nCount++;
else if (strInput[j] == ')')
nCount--;
if (nCount < 0)
{
bAns = false;
break;
}
else if (j == strInput.length() && nCount == 0)
{
bAns = true;
break;
}
}
if (nCount != 0)
bAns = false;
if (bAns)
printf("YES\n");
else if (!bAns)
printf("NO\n");
nCount = 0;
bAns = true;
}
}
ㄱ
검토는 딱히 안했다. 문제를 여러개를 몰아 푸느라 가장 최상단의 for문과 변수들은 대부분 놔두었는데 이대로만 해도 맞았다고 표시되니 검토 안함.
'# 공부 > # 알고리즘' 카테고리의 다른 글
[큐,덱]#11866 c++ 요세푸스 (0) | 2021.04.09 |
---|---|
#2146 c++ 백준 알고리즘 간단한 설명 및 코드 (0) | 2021.04.06 |
[스택] 제로 :: 백준알고리즘 10773번 c++ (0) | 2021.01.17 |
[스택] 백준알고리즘 10828번 c++ (0) | 2021.01.17 |
[정렬] MergeSort 병합정렬 (0) | 2021.01.16 |