[백준,C++] 4949: 균형잡힌 세상

 

728x90

문제

---

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

SMALL

입력

---

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

반응형

출력

---

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입력 1

---

 

So when I die (the [first] I will see in (heaven) is a score list). [ first in ] ( first out ). Half Moon tonight (At least it is better than no Moon at all]. A rope may form )( a trail in a maze. Help( I[m being held prisoner in a fortune cookie factory)]. ([ (([( [ ] ) ( ) (( ))] )) ]). . .

 

예제 출력 1

---

 

yes yes no no no yes yes

 

 

문제를 처음 접했을 때는 스택을 이용한 간단한 접근을 시도했지만, 이후에 문자열 입력에 대한 이해 부족을 느꼈습니다. 문제 해석 능력과 문자열 입력 처리 능력의 부족이 복합적으로 문제를 해결하는 데 어려움을 주었습니다. 이런 상황에서는 파이썬으로 전환하는 것이 도움이 될 수 있습니다.

 

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {

	while(true){
		stack<char> S;
		string str;
		
		getline(cin, str);
		
		if(str==".")
			break;
	
		bool flag = true;
			
		for(int i=0; i<str.size(); i++){
			
			if(str[i] == '[' || str[i] == '('){
				S.push(str[i]);
			}
			
			else if(str[i] == ']'){
				if(S.empty()){
					flag = false;
					break;
				}
				
				else if(S.top() == '['){
					S.pop();
				}
				
				else if(S.top() == '('){
					flag = false;
					break;
				}
			}
			
			else if(str[i] == ')'){
				if(S.empty()){
					flag = false;
					break;
				}
				
				else if(S.top() == '('){
					S.pop();
				}
				
				else if(S.top() == '['){
					flag = false;
					break;
				}
			}
			
		}
		
		if(S.empty() && flag)
			cout << "yes"<<'\n' ;
			
		else
			cout << "no"<<'\n' ;
	
	}

	return 0;
}

 

결국 위과 같은 코드로 해결했는데

 

알고리즘 자체는 '('나'['의 입력에는 나중에 닫아줘야하는애들이기에 스택에 Push해주고

')'가 입력되면 대응하는 '('가 스택에 있으면 닫아주면 되지만

'['나 스택이 empty 하면 틀렸다고 판단내릴 수 있는

 

Stack 문제이다

 

그럼 String Input에 대해 좀 더 알아보자

 

 

while(true){
		stack<char> S;
		string str;
		
		getline(cin, str);
		
		if(str==".")
			break;

 

입력을 받는 부분에서 변수 설정을 제외하고 getline() 함수를 사용하여 한 줄씩 입력을 받아 str에 저장하는 방식으로 문자열을 처리하는 것으로 이해했습니다. 이렇게 하면 개행 문자나 엔터 키가 인식될 때까지 문자열을 입력받고, '.' 하나만 입력되면 while문을 탈출하여 프로그램이 종료됩니다. 

문제에서 '.'은 문자열이 sub-string들로 분리되어 있는 것처럼 설명되었지만, 실제로는 의미가 없는 온점일 뿐이며, 문제의 정답에 영향을 미치지 않습니다. 따라서 getline() 함수를 사용하여 한 줄씩 입력을 받는 것이 올바른 접근입니다. 이렇게 하면 입력을 효율적으로 처리할 수 있고, 문자열 입력에 대한 이해도 높일 수 있습니다.

 

<[백준,C++]  11050: 이항계수>

https://tonnykang.tistory.com/94

[백준,C++] 11050 : 이항계수