[C++백준] 실버 4/ 4949번 균형잡힌 세상

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

#include <iostream>
#include<istream>
#include<algorithm>
#include <string>
#include <stack>
 
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    while (true) {
        stack<char>stack;
        string s;
        getline(cin, s);//한줄씩 입력받아줌 
        if (s == ".") { //점이면 break
            break;
        }
        
        bool balance = true;
        for (int i = 0; i < s.size(); i++) {
            if ((s[i] == '(') || (s[i] == ')')) {
                if (s[i] == '(')
                    stack.push(s[i]);
                else if (s[i] == ')')
                    if (stack.empty()) {
                        balance = false;
                        break;
                    }
                    else if (stack.top() == '(') {
                        stack.pop();
                    }
                    
                    else if (stack.top() != '(') {
                        balance = false;
                    }
                    
            }
 
            if ((s[i] == '[') || (s[i] == ']')) {
                if (s[i] == '[')
                    stack.push(s[i]);
                else if (s[i] == ']') {
                    if (stack.empty()){
                        balance = false;
                        break;
                    }
                    else if (stack.top() == '[') {
                        stack.pop();
                    }
                    else if (stack.top() != '[') {
                        balance = false;
                    }
                }
 
 
            }
 
        }
        if (balance&&stack.empty()) {
            cout << "yes" << endl;
 
        }
        else {
            cout << "no" << endl;
        }
        
 
 
 
    }
 
 
    return 0;
}
 

 

이 문제는 스택으로 풀었다. 괄호 문제가 나오면 자동으로 스택으로 풀게되는 것 같다 ㅋㅋ

 

문제를 풀면서 주의할 점 

우선 이 문제는 반례를 최대한 고려하지 않으면 20%에서 틀렸습니다가 나온다. 백준 질문 게시판에 있었던 글 중에 나에게 유용했던 반례는

][]

(])

 

였다.  만약에 막히시는 분이 있다면 이 두 반례가 좋은 도움이 될 수도 있어요..!

 

사실 '['나 '(' 가 들어올 때는 큰 문제가 되지 않지만 중요한건 ']'과 ')'가 들어올 때인것 같다.

 

나는 3가지로 케이스 분류를 해봤는데

만약에 stack이 비어있다면 가차없이 끝내준다.

만약에 stack 윗부분이 '('라면 짝이 맞는 것이므로 '('을 꺼내주면 된다.

스택은 후입선출 구조이기 때문에 맨 위만 고려해주면 된다

이 부분이 날 골치아프게 했다. 처음엔 continue를 써서 넘겨줬는데 이건 내가 stack의 특징을 제대로

생각하지 않은 탓이였다. stack은 맨 위에 있는 애만 가지고 판단을 한다.

 

만약에 )가 들어가는데 맨위가 '['가 들어있다면 애초에 ')'는 얘랑 짝이되는 '('가 없기에 이미 균형이 깨진다.

반례로 예를 들면 [ ) ] 가 있다.
}

 

 

 

C++ STL라이브러리의 Stack 

https://coding-factory.tistory.com/597

[C++] STL Stack 사용법 & 예제 총정리

 

 

getline()

 

getline()함수는 istream라이브러리에 속하거나  string라이브러리에 속해있는 경우,

총 2가지 경우가 있다. 나는 istream 라이브러리에 속해있는 것을 사용했다.

 

getline은 줄바꿈을 하는 문장을 입력받을 때,띄어쓰기가 포함된 문장을 입력받을 때 보통 사용한다. 문자열을 줄 단위로 입력받고 싶을 때 사용하면 된다.

 

 

java로 풀 때

 

 

 
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
 
    public static String Solve(String s){
        //스택 초기화
        Stack<Character>stack=new Stack<Character>();
 
        for(int i=0;i<s.length();i++){
            Character c=s.charAt(i);
            if(c=='('||c=='['){
                stack.push(c);
 
            }
            else if(c==')'){
                if(stack.isEmpty()){
                    return "no";
                }else if(stack.peek()=='('){
                    stack.pop();
                }else if(stack.peek()!='('){
                    return "no";
                }
            }
            else if(c==']'){
                if(stack.isEmpty()){
                    return "no";
                }else if(stack.peek()=='['){
                    stack.pop();
                }else if(stack.peek()!='['){
                    return "no";
                }
            }
        }
        if(stack.isEmpty()){
            return "yes";
        }else{
            return "no";
        }
 
 
    }
    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
 
        String s;
 
        while(true) {
            s=sc.nextLine();
            if(s.equals(".")){
                break;
            }
            System.out.println(Solve(s));
 
 
        }
 
    }
 
 
 
}
 
 
 
 
 
 
 
 
 
 
 
 
 

 

분명 C++로 풀었는데 문제를 풀면서 두가지를 놓쳤다.

 

1. ([)] --> 이건 균형잡힌게 아니다. 나는 저 예시도 맞는 줄 알고 스택 두개 써서 풀었는데 애초에 문제를 잘못 이해한거였음 ㅇㅇ

 

2. 자바 scanner에서 입력받을 때 next()와 nextLine()의 차이점을 이해하지 못했음

next()는 스페이스 전까지 입력받은 문자열을 리턴하는 것이고, nextLine()은 enter치기 전까지 쓴 

문자열을 모두 리턴하는 것이다. 

 

3. 마지막에 stack이 비어있는지 확인해줘야하는 이유

 if(stack.isEmpty()){

            return "yes";

        }else{

            return "no";

        }

 

예를 들어 )( 가 들어왔는데 ) <--얘는 당연히 스택에 쌓이지 않을 거고 ( <--얘 같은 경우는 스택에 쌓일거다.

그러면 스택이 비어있는지 확인해주지 않으면 )( 같은 경우도 "yes"가 리턴될 것이다.