[ Algorithm ] 백준 4949번 : 균형잡힌 세상 - [JAVA]

Minsu Lee·2023년 2월 15일

Java algorithm

baekjoon

목록 보기

6/16

🎆4949번 균형잡힌 세상🎆

📌문제

🔍 문제 설명

문제 링크: https://www.acmicpc.net/problem/4949

🔍예제 입력

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)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

🔍예제 출력

yes
yes
no
no
no
yes
yes

📌풀이

🔍풀이 설명

자료 구조 (Date-Structure)를 이용하여 푸는 문제였다. Stack사용

Stack : 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조
스택(Stack)는 LIFO(Last In First Out) 를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

pop(): 스택에서 가장 위에 있는 항목을 제거한다.

push(item): item 하나를 스택의 가장 윗 부분에 추가한다.

peek(): 스택의 가장 위에 있는 항목을 반환한다.

isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

스택의 LIFO 특성을 이용해 대괄호와 소괄호가 열리는 기호인 경우 스택에 넣고 닫히는 경우는 스택에 들어있는 것을 꺼내 비교해서 균형이 잡힌 건지 확인하는 방식으로 풀었다. 입력받은 문장은 BufferedReader의 readLine()을 이용했고 charAt()으로 하나하나 비교했다.

🔍코드

package Data_Structure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

//균형잡힌 세상
public class p4949 {
    static Stack<Character> stack;
    static String balanced_world (String s) {
        String result;
        stack = new Stack<>();

        for (int i=0; i<s.length(); i++){
            char a = s.charAt(i); //char형으로 하나씩 검사!

            if(a=='['|| a=='('){ //여는 괄호일 경우 스택에 추가
                stack.add(a);
            }

            else if(a==']'){ //닫는 대괄호인 경우
                if(stack.isEmpty() || stack.peek() !='['){
                    //스택이 비어있거나 짝이 맞지 않는 경우 no 리턴
                    result = "no";
                    return result;
                }
                else {
                    stack.pop();
                }
            }
            else if (a==')'){//닫는 소괄호 경우
                if(stack.isEmpty() || stack.peek() !='('){
                    //스택이 비어있거나 짝이 맞지 않는 경우 no 리턴
                    result = "no";
                    return result;
                }
                else {
                    stack.pop();
                }
            }
            else{ //괄호가 아닌 것들은 전부 패스!
                continue;
            }
        }
        //for문 종료 후 스택에 아무것도 남지 않았다면 균형잡힌 문장!
        if(stack.isEmpty()){
            result = "yes";
        }
        else {
            result = "no";
        }

        //결과 리턴!
        return result;
    }
    public static void main(String[] args) throws IOException{
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s;
        while(true){
            s = br.readLine();
            //종료 조건 "." 하나 입력
            if(s.equals(".")){
                break;
            }

            //문장 검사
            String result = balanced_world(s);
            sb.append(result).append("\n");
        }
        System.out.print(sb);
    }
}