문제 하나 공유

쉽지만 처음엔 떠올리기 힘든 간단한 로직을 보여드릴게욥

 

알 사람들은 다 아는 괄호 문제입니다. 포인터 공부하다가 만난 문제인데 사실 포인터 필요 없어요...

예를 들어

()() - 올바른 괄호

(())() - 올바른 괄호

)()() - 틀린 괄호

(())) - 틀린 괄호

 

이 처럼 짝이 안맞거나 닫힌 괄호로 시작하거나 열린 괄호로 끝나면 틀린 괄호입니다.

 

저는 그저 괄호를 만나면 카운트 수를 조정하는 방식을 사용했습니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
char a[100001];
int main()
{
	int i, l, c = 0;
	scanf("%s", a);

	l = strlen(a);

	for (i = 0;i < l;i++) {
		if (a[i] == '(') c++;
		else if (a[i] == ')') c--;
		if (c < 0) break;
	}
	if (c == 0) printf("true");
	else printf("false");

	return 0;
}

이렇게 잘 됩니당.

---

 

C++에서는 이런식으로도 작성해보았습니다.

#include<bits/stdc++.h>
using namespace std;

char br[50001];

int main()
{
	int c=0,len;
	string br;
	cin >> br;
	
	len = br.length();
	
	for(int i=0; i<len; i++){
		if(br[i]=='(') c++;
		else if(br[i]==')') c--;
		if(c<0) break;
	}
	
	if(c==0) cout << "good";
	else cout << "bad";
	return 0;
}

사실 로직은 똑같습니다. 형태만 다르지

 

다른 방법으로 2개 더 있습니다.

#include<bits/stdc++.h>
using namespace std;

char stk[50001];

int main()
{
	int sp=0;
	string str;
	cin >> str;
	
	for(auto c: str){
		if(c=='(')
			stk[sp++]=c;
		else{
			if(sp==0 || stk[sp-1]==c) stk[sp++] = c;
			else sp--;
		}
	}
	if(sp==0) cout<<"good";
	else	  cout<<"bad";
	
	return 0;
}

이것도 로직은 비슷합니다 대신에 for auto를 사용했습니다.

 

정말 신박한 방법은 이것입니다.

#include<bits/stdc++.h>

using namespace std;

vector<char> stk;

int main()
{
	string str;
	cin >> str;
	
	for(auto c: str){
		if(c=='(')
			stk.push_back(c);
		else{
			if(stk.empty() || stk.back()==c) stk.push_back(c);
			else stk.pop_back();
		}
	}
	if(stk.empty()) cout<<"good";
	else	  cout<<"bad";
	
	return 0;
}

사실 이정도 뇌절했으면 느끼셨을테지만 모두 로직이 같습니다. ㅎㅎ

열린 괄호는 넣거나 카운트를 올리고 반대는 빼주고 중간중간 비었는데 닫힌 괄호면 포함 안하고 끝입니다.

 

문법만 달라지지 로직은 같다는 것을 이미 아셨다면 베리 굿

 

모를 분들을 위해 마지막 코드를 짧게 설명하자면

Vector라는 자료형입니다! 쉽게 말하면 길이가 가변이고 인덱스가 아닌 주소를 사용하는 배열입니다. 벡터를 통해 스택이라는 자료형의 형태를 이용해 만든 것입니다.

 

스택은 LIFO 순서의 자료형입니다. 늦게 들어온 것이 먼저 나가는, 출구와 입구가 동일한 자료구조입니다.

 

반복문을 돌리면서 문자가 '(' 이면은 push_back(c), 배열열에 '(' 를 넣습니다(c++과 같음).

반대로 ')'이면 배열에서 빼버리고 최종적으로 비어있으면 완벽하다 이겁니다. 

 

이를 위해 중간에 닫힌 괄호가 입력되었을 때 직전 문자가 닫힌 괄호거나(마지막에 열린괄호로 끝나면 틀린것이기 때문), 비어있다면 넣습니다. (닫힌 괄호로 시작은 괜찮아요, 짝만 맞으면 되서)

둘다 아니면 그저 순서가 잘 맞은 괄호이기에 pop_back()을 해줍니다(요소 제외).

 

최종적으로 비어있다면 짝을 모두 찾은 것이기에 완료됩니다.