[백준] 4949-균형잡힌 세상-Java

24 Jun 2023 in Algorithm on Algorithm

[백준] 4949-균형잡힌 세상-Java

---

❓문제

입력받은 문자열에서 소괄호(“(“, “)”)와 대괄호(“[”, “]”)가 올바르게 VPS(Valid Parenthesis String)를 이루는지 확인하고, 각 문자열이 VPS인 경우, “yes”를 VPS가 아닌 경우 “no”를 출력하면 된다.
이때 입력의 종료조건은 온점 하나(“.”)가 입렫된다.

🖊️풀이법

간단하다. 앞서 풀었던 괄호는 Stack의 성질을 이용하면 간단하게 풀 수 있으며, 각 문제가 제시하는 조건을 의사코드로 작성한 후 코드로 순서대로 구현하면 된다.

1. 문자열이 온점 하나가 아닌경우 반복문을 계속 순회, 온점 하나가 입력될 경우 반복문을 종료한다.
2. 만약 입력받은 문자열을 순회하는 동안 괄호를 여는 ( 나 [가 입력될 경우, 스택에 push 한다.
3. 만약 입력받은 문자열을 순회하는 동안 닫는 괄호 ) 나 ]가 입력될 경우, 스택의 peek를 확인 후 올바른 여는 괄호가 peek인 경우, 스택을 pop한다. peek가 올바른 여는 괄호가 아닌 경우, 해당 반복문을 종료하고, “no”를 리턴한다.
4. 스택이 비어있는 경우 ) 나 ]가 입력된 경우에도, 반복문을 종료하고, “no”를 리턴한다.
5. 입력받은 문자열의 길이만큼 반복문을 모두 순회하면, 올바른 VPS문장이므로 “yes”를 리턴한다.

정답 코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true) {
            String str = br.readLine();
            if(str.equals(".")){
                break;
            }
                sb.append(match(str)).append('\n');
        }
        System.out.println(sb);
    }
    static String match(String str){
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0 ; i < str.length() ; i++){
            char c = str.charAt(i);
            if(c == '[' || c == '('){
                stack.push(c);
            } else if (c == ']'){
                if(stack.empty() || stack.peek() != '['){
                    return "no";
                } else if(stack.peek() == '['){
                    stack.pop();
                }
            }

            else if (c == ')'){
                if(stack.empty() || stack.peek() != '('){
                    return "no";
                } else if(stack.peek() == '('){
                    if(stack.empty()){
                        return "no";
                    }
                    stack.pop();
                }
            }
        }
        if(!stack.empty()){
            return "no";
        } else {
            return "yes";
        }
    }
}

---

정리

항상, 알고리즘을 풀 때는 의사코드를 잘 작성하여, 계획한 뒤 코드로 구현하는 것이 참 중요한 것 같다 :)
복잡한 문제일수록 문제를 단순히 하고, 올바른 의사코드를 작성하는 습관을 들이자.