[백준 / Java] 4949번: 균형잡힌 세상 (실버4)

문제 풀이 날짜: 2023.05.23
포스트 작성일: 2023.05.24

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 4949번: 균형잡힌 세상 (실버4) (문제 링크)

 

키워드

스택

 

풀이 접근법

• 괄호는 스택으로 짝을 지으면 된다.
• 괄호가 하나도 존재하지 않는 문자도 균형 잡힌 문자이다.
• 괄호의 짝이 맞지 않은 것을 하나라도 발견한다면 즉시 탐색을 멈춘다. (반복문 탈출)
• 그렇다면 스택으로 괄호의 짝을 어떻게 맞출까?
  • 왼쪽 괄호를 만나면 스택에 넣는다.
  • 오른쪽 괄호를 만나면 스택에서 괄호를 하나 poll()하고 그것이 왼쪽 괄호와 짝이 맞는지 확인한다.
  • 스택의 가장 마지막에 넣었던 것이 스택 최상단에 위치하므로, 이렇게 대칭 여부를 판단할 수 있다.
• 주의: 입력으로 괄호의 개수가 부족한 케이스도 준다.
  • 탐색을 모두 마쳤는데 스택에 남은 괄호가 있다면 입력된 괄호의 개수가 부족한 것이다. 이 경우를 처리해주어야 한다. 매 반복이 끝날 때마다 스택도 잘 비워준다.

 

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		ArrayList<String> sentences = new ArrayList<>();
		
		while(true) {
			String line = br.readLine();
			
			if(line.equals(".")) {
				break;
			}
			
			sentences.add(line);
		}
		
		Stack<Character> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		
		boolean balanced = true;
		for(String sentence : sentences) {
			int length = sentence.length();
			
			for(int i = 0; i < length; i++) {
				char c = sentence.charAt(i);
				
				if(c == '(' || c == '[') {
					stack.push(c);
				}
				
				if(c == ')' || c == ']') {
					if(stack.size() <= 0) {
						balanced = false;
						break;
					}
					
					char bracket = stack.pop();
					
					if(!matches(c, bracket)) {
						balanced = false;
						break;
					}
				}
			}
			
			if (stack.size() > 0) {
				sb.append("no").append('\n');
			}
			else if(balanced == true) {
				sb.append("yes").append('\n');
			}
			else if(balanced == false) {
				sb.append("no").append('\n');
			}
			
			balanced = true;
			stack.clear();
		}
		
		System.out.print(sb);
	}

	private static boolean matches(char c, char bracket) {
		if(bracket == '(' && c == ')'
			|| bracket == '[' && c == ']') {
			return true;
		}
		
		return false;
	}

}

---

스택의 응용문제 중에서 가장 간단한 유형 중 하나이다. 이 외에도 어떤 문제에서는 물건의 구매와 판매, 돈의 입출금 등의 동작을 0, 1로 구분하여 짝지어야 하는 경우도 생긴다. 그러한 경우에도 스택을 잘 이용해주어야 한다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week9/day2/Q4949.java