궤도
[백준] 4949번 : 균형잡힌 세상 본문
문제
풀이
[백준] 9012번 : 괄호
문제 풀이 스택 문제에는 나혼자 정했지만 아마 일반화도 가능할 듯한 네임드 문제 2개가 있다. 후위표기법 사칙연산과 괄호 맞추기다. 유명한 문제들이니만큼 풀이법도 세뇌수준으로 들어서
myunji.tistory.com
이 문제의 응용판이다.
사실 이 문제에서 제일 어려운건 입력을 처리하는 것이다.
괄호야 뭐...왼쪽 괄호 나오면 스택에 쌓고 오른쪽 괄호 나오면 짝 맞는지 확인해서 pop하면 그만이다.
그럼 띄어쓰기가 있는 입력을 어떻게 처리할지 살펴보자.
소스코드
#include <iostream>
#include <stack>
#include <string>
using namespace std;
void bracket(string input, int length) {
stack<char> s;
for (int i = 0; i < length; i++) {
if (input[i] == '(' || input[i] == '[') //왼쪽 괄호면 push
s.push(input[i]);
else if (input[i] == ')') { //오른쪽 괄호면 pop인데
if (s.empty() || s.top() != '(') { //아무것도 없거나 짝 안맞는지 확인
cout << "no\n";
return;
}
s.pop();
} else if (input[i] == ']') { //위와 같음
if (s.empty() || s.top() != '[') {
cout << "no\n";
return;
}
s.pop();
}
}
if (s.empty()) //스택이 비어있으면 다 짝이 있었다는 뜻
cout << "yes\n";
else
cout << "no\n";
}
int main() {
string input;
while (true) {
getline(cin, input); //띄어쓰기까지 받는 방법
if (input.compare(".") == 0)
break;
bracket(input, input.size());
}
}전체 소스코드다.
int main() {
string input;
while (true) {
getline(cin, input); //띄어쓰기까지 받는 방법
if (input.compare(".") == 0)
break;
bracket(input, input.size());
}
}문자열은 input에 받을 것이다. 평소같았으면 cin>>input으로 입력을 받았겠지만 띄어쓰기까지 받기 위해 getline 함수를 쓸 것이다.
www.cplusplus.com/reference/string/string/getline/
getline (string) - C++ Reference
function std::getline (string) (1)istream& getline (istream& is, string& str, char delim); (2)istream& getline (istream& is, string& str); (1)istream& getline (istream& is, string& str, char delim); istream& getline (istream&& is, string& str, cha
www.cplusplus.com
getline 함수는 이런 함수다.
뭔지 잘 모르겠으면
이것만 봐도 된다. 우린 input에 넣을거니까 두번째 인자로 input을 넣어준다.
3번째 인자를 넣을 수도 있는데, 3번째 인자는 입력을 종료할 지점(?)을 지정하는 것이다.
만약 3번째 인자로 'a'를 넣었다면 befdage를 입력했을 때 befd가 들어올 것이다.
default값은 '\n'이다.
void bracket(string input, int length) {
stack<char> s;
for (int i = 0; i < length; i++) {
if (input[i] == '(' || input[i] == '[') //왼쪽 괄호면 push
s.push(input[i]);
else if (input[i] == ')') { //오른쪽 괄호면 pop인데
if (s.empty() || s.top() != '(') { //아무것도 없거나 짝 안맞는지 확인
cout << "no\n";
return;
}
s.pop();
} else if (input[i] == ']') { //위와 같음
if (s.empty() || s.top() != '[') {
cout << "no\n";
return;
}
s.pop();
}
}
if (s.empty()) //스택이 비어있으면 다 짝이 있었다는 뜻
cout << "yes\n";
else
cout << "no\n";
}char형의 값을 담을 스택 s를 선언한다.
왼쪽 괄호들이 들어왔다면 그대로 스택에 넣어주고, 오른쪽 괄호가 들어왔을 때는 스택의 top에 있는 값이 해당 괄호와 짝이 맞는 왼쪽 괄호인지 확인한다. 짝이 맞지 않거나 스택이 비어있다면 올바른 괄호짝이 아닌 것이다.
문자열을 다 조회한 뒤 스택에 여전히 값이 남아있다면 이 역시 올바른 괄호가 아니다.
