#4949 : 균형잡힌 세상

풀이방법

사용된 것:

Stack

 

2022.04.29

 

#9012 : 괄호

백준 9012번 괄호 문제와 매우 비슷한 문제이다.​

 

각 문자열마다 아래의 과정을 수행하면 된다.

 

boolean 형 변수 v를 true로 초기화해준 뒤, 문자열이 균형잡히지 않았다는 것이 발견되면 false로 바꾸어줄 것이다.

마지막에 v의 값이 true인 상태로 남아있다면 해당 문자열은 균형잡힌 것이다.

 

주어진 문자열을 처음부터 한 글자씩 살핀다.

 

이번 문자가 '(' 혹은 '['라면 스택에 해당 문자를 추가한다.

이번 문자가 ')' 혹은 ']'라면 스택의 top에 있는 문자가 이번 문자와 쌍을 이루는 왼쪽 괄호인지 확인한다. 만약 그렇다면 스택에서 문자 하나를 pop() 하고 다음 글자로 넘어간다. 그러나 엉뚱한 문자가 top에 있거나 스택이 비어있다면 이 문자열은 균형잡힌 문자열이 아니다. 뒤의 문자들은 살펴볼 필요도 없다. v를 false로 바꾸고 이번 문자열의 점검을 끝낸다.

 

스택에 top에 엉뚱한 문자가 있거나 비어있어서 중간에 빠져나오는 일 없이 끝까지 점검을 마쳤다고 해도 끝이 아니다.

점검을 무사히 마쳤을 때 스택이 비어있어야 이 문자열은 균형잡힌 문자열이다.

따라서 스택이 비어있는지 확인해준다.

스택이 비어있지 않다면 v를 false로 바꾼다.

 

위의 과정을 마쳤을 때 v의 값이 true라면 그 문자열은 균형잡힌 문자열이다. 출력 문자열에 "yes"를 추가한다.

v의 값이 false라면 그 문자열은 균형잡힌 문자열이 아니다. 출력 문자열에 "no"를 추가한다.

 

코드

Java(2022.04.29)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		while(true) {
			//입력값이 "."이라면 입력이 끝난 것이므로 종료함
			String str = br.readLine();
			if(str.equals(".")) break;
			
			boolean v = true;	//균형을 이루는 문자열인지 판별하는 데 쓰는 boolean 변수
			Stack<Character> stack = new Stack<Character>();	//스택 선언
			
			//문자열의 모든 문자에 대해 앞에서부터 반복
			for(int i = 0; i<str.length(); i++) {
				char t = str.charAt(i);
				
				//'(' 또는 '['일 경우 스택에 넣기
				if(t == '(') stack.add('(');
				else if(t == '[') stack.add('[');
				
				//')' 또는 ']'일 경우 짝이 맞는 왼쪽 괄호가 스택의 top에 있을 때만 ok
				//그렇지 않으면 즉시 v를 false로 바꾸고 문자열 점검을 종료
				else if(t == ')') {
					if(stack.isEmpty()) {v = false; break;}
					if(stack.peek() == '(') stack.pop();
					else {v = false; break;}
				}
				else if(t == ']') {
					if(stack.isEmpty()) {v = false; break;}
					if(stack.peek() == '[') stack.pop();
					else {v = false; break;}
				}
			}
			
			//문자열을 끝까지 살폈는데 스택이 비어있지 않으면 균형을 이루는 것이 아님
			if(!stack.isEmpty()) v = false;
			
			//v의 값을 점검하여 yes 혹은 no를 출력 문자열에 추가
			if(v) sb.append("yes");
			else sb.append("no");
			sb.append(System.lineSeparator());
		}
		
		//정답 출력
		System.out.print(sb);

	}

}