[Stack][Java][BOJ] #4949. 균형잡힌 세상

#스택  #Silver4

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

 

🌷 문제 설명

✏️ 백준 연습문제: #4949. 균형잡힌 세상
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

⌨️ 입력
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

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

입출력 예

입력	출력
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

 

💡 해결 포인트

1.  스택에서 사용할 수 있는 메서드 
- .push()
- .isEmpty()
- .peek() 맨 위 요소를 반환하는데, pop이랑 다르게 제거하진 않음
- .pop()

 

🌷 내 코드

1. 스택

import java.io.*;import java.util.*;public class BOJ_2343 {    public static void main(String[] args) throws IOException {        System.setIn(new FileInputStream("example.txt"));        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        // 첫 번째 줄 입력        String[] firstLine = br.readLine().split(" ");        int N = Integer.parseInt(firstLine[0]); // 강의의 갯수        int M = Integer.parseInt(firstLine[1]); // 블루레이의 갯수        // N개 강의의 길이 입력(강의 순서대로, 분 단위(자연수)로 주어짐)        int[] numbers = new int[N];        String [] thirdLine = br.readLine().split(" ");        for (int i = 0; i < N; i++) {            numbers[i] = Integer.parseInt(thirdLine[i]);        }        // M개 블루레이의 길이 입력        int left = Arrays.stream(numbers).max().getAsInt(); // 블루레이에 들어있는 값 중 가장 긴 강의 길이        int right = 1,000,000,000; // 가능한 최댓값(N의 최댓값 * M의 최댓값)        int answer = 0;        while (left <= right) {            int mid = (left + right) / 2; // 블루레이의 길이            int sum = 0; // 블루레이에 담긴 강의 길이 합            int cnt = 1; // 블루레이 개수            for (int i = 0; i < N; i++) { // 강의 길이만큼 반복                if (sum + numbers[i] > mid) { // 블루레이에 담긴 강의 길이가 블루레이의 길이보다 크면                    cnt++; // 블루레이 개수 증가                    sum = 0; // 블루레이 초기화                }                sum += numbers[i]; // 블루레이에 담긴 강의 길이 추가                // System.out.println("sum: " + sum + ", cnt: " + cnt + ", mid: " + mid + ", left: " + left + ", right: " + right + ", answer: " + answer);            }            if (cnt <= M) { // 블루레이 개수가 M개 이하이면                answer = mid; // 결과값에 블루레이의 길이 저장                right = mid - 1; // 블루레이의 길이를 줄임            } else { // 블루레이 개수가 M개보다 크면                left = mid + 1;             }        }        System.out.println(answer);    }}import java.util.*;
import java.io.*;

public class BOJ_4949 {
  public static void main(String[] args) throws IOException{
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    while (true) { // 몇 줄 들어오는지 모르니까
      String line = br.readLine();
      if (line.equals(".")) break; // 종료 조건

      Stack<Character> stack = new Stack<>(); // Char
      boolean isBalanced = true;

      for (int i = 0; i < line.length(); i++) {
        char c = line.charAt(i);
        
        if (c == '(' || c == '[') {
          stack.push(c);
        } else if (c == ')') {
          if (stack.isEmpty() || stack.peek() != '(') {
            isBalanced = false;
            break;
          }
          stack.pop();
        } else if (c == ']') {
          if (stack.isEmpty() || stack.peek() != '[') {
            isBalanced = false;
            break;
          }
          stack.pop();
        }
      }

      if (isBalanced && stack.isEmpty()) {
        System.out.println("yes");
      } else {
        System.out.println("no");
      }
    }

  }
}

 

🌷 코멘트

ㅋㅋ 골드는 아무리 남의 코드 봐도 잘 모르겠어서 쉬운 길로 왔다.. 아아 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com