[Baekjoon] 4949 - 균형잡힌 세상

📝 문제

 

 

🔑 풀이 과정

이 문제는 9012번 문제였던 괄호문제와 풀이방식이 거의 동일하다고 보면 된다.

9012번 풀이는 여기 ↓. 이걸 보는 것을 추천

https://seohyun0916.tistory.com/254

[Baekjoon] 9012 - 괄호

 

9012번과의 차이점

ⓛ 9012번 문제는 테스트케이스가 몇 개 들어오는지 주어진다.

이번 4949번 문제는 개수가 주어지지 않고, 온점 하나(".")를 입력받으면 입력이 종료된다.

→ 무한 루프를 사용해서 계속 입력받고, 만약 입력받은 문자열이 온점 하나(".")면 입력 종료

 

② 9012번 문제는 입력 데이터가 무조건 괄호 () 로만 이루어져 있다.

이번 4949번 문제는 영문 알파벳, 공백, 괄호가 섞여있다.

→ 문자열의 문자를 하나하나 순회하면서 '(', ')', '[', ']' 일때의 경우를 작성해주고, 그렇지 않으면 다음 문자로 넘어가게 한다. (괄호 4가지 경우가 아니면 고려하지 않는다는 뜻!)

 

③ 9012번 문제는 괄호가 소괄호로 한 종류이다.

이번 4949번 문제는 괄호가 소괄호(), 대괄호[]로 두 가지 종류이다.

→ 여는 괄호 (, [ 인 경우는 종류 상관없이 push 해주고, 닫는 괄호 ), ] 인 경우는 종류를 나눠서 생각해준다.

닫는 괄호 ) 인 경우에는 여는 괄호 (와 짝이 맞아야 한다.

(1) 스택이 비어있으면 짝이 맞는 여는 괄호가 없음

(2) 스택의 가장 위가 여는 괄호 ( 여야함. 여는 괄호 [ 면 짝이 맞지 않음.

이 두가지 상황을 고려해서 코드를 작성해준다.

 

 

🔓 답안

import java.io.*;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while(true){
            String str = br.readLine();

            //온점 하나 들어오면 입력 종료
            if(str.equals("."))
                break;

            if(isBalanced(str))
                bw.write("yes\n");
            else
                bw.write("no\n");

        }

        bw.flush();
        bw.close();
    }

    static boolean isBalanced(String str){

        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < str.length(); i++){
            switch(str.charAt(i)){
                case '(':
                case '[':
                    stack.push(str.charAt(i));
                    break;
                case ')':
                    if((stack.size() == 0) || stack.peek() != '(')
                        return false;
                    else
                        stack.pop();
                    break;
                case ']':
                    if((stack.size() == 0) || stack.peek() != '[')
                        return false;
                    else
                        stack.pop();
                    break;
                default: // []() 말고 다른 문자일 경우 고려하지 않음
                    break;
            }
        }

        if(stack.isEmpty())
            return true;
        else   //문자열을 다 순회하고도 스택이 비어있지 않다면, 짝이 맞지않는 괄호가 남아있다는 뜻
            return false;

    }

}

 

 

 

🖤 알고리즘 분류

- 자료 구조

- 문자열

- 스택