[백준] 단계별로 풀어보기(단계:18,스택,JAVA)4949번, 균형잡힌 세상

문제 링크

4949번: 균형잡힌 세상

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

기본적으로 스택이란 LIFO(후입 선출)의 자료구조입니다.

LIFO는 먼저 들어간 데이터들이 출력할 때 나중에 나온다는 이야기입니다.

예를 들어 3, 2, 1을 순서대로 스택에 저장한 뒤 하나씩 꺼내보겠습니다.

1. 스택에 3을 넣었을 때

3

2. 스택에 2을 넣었을 때

2

3

3. 스택에 1을 넣었을 때

1

2

3

4. 스택에 하나의 자료를 출력하라는 명령이 떨어졌을 때

1

2

3

5. 다시 자료를 출력하라는 명령이 떨어졌을 때

2

3

위에 표를 보면 간단히 돌탑을 생각하시고 돌을 뺄 때 나중에 올린 돌부터 빼는 것처럼 스택은 LIFO의 형태를 가진 자료구조입니다.

 

이 문제에서는 '('와 '['가 들어왔을 때에는 스택에 push을 진행하고 ')'와 ']'가 들어오면 pop을 진행하도록 하는 문제입니다.

push와 pop을 사용하는 스택을 사용하였습니다. = Stack<char> 형태

'('와 '['가 입력되었을 때 Stack.push()를 사용하였으며 ')'와 ']'가 입력되었을 때에는 Stack.pop()을 사용하였습니다.

모두 짝을 이루고 있다면 Stack에 들어간 값들이 모두 pop이 되었을 것이므로 비어있어야 합니다.

그래서 받은 문자열이 VPS인지 확인을 위해 Stack.empty()을 사용하였습니다.

마지막으로 이 문제에 입력된 문자열에 관하여 괄호는 균형을 맞추어야 합니다.

그래서 가장 최근에 '('가 입력되었다면 ')'가 나와야 하며 '['가 입력되었다면 ']'가 나와야 균형을 맞출 수 있습니다.

Stack.peek()을 사용하여 가장 최근에 추가한 괄호를 기준으로 다른 기호로 괄호가 닫히게 된다면 VPS가 아닌 것을 판명할 수 있습니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 입력값이 "."인 경우는 반복을 종료하도록 하였습니다.
• 받은 문자열을 String.CharAt()을 사용하여 어떤 문자인지 확인하였습니다.
• '('와 '['을 받으면 push, ')'와 ']'을 받으면 pop을 진행하였습니다.
• 스택에 push/pop을 하는 함수 stackPush/stackPop을 만들었습니다.
• 받은 문자열이 VPS인지 확인하는 함수 VPS()을 만들었습니다.
• 함수 결과값을 BufferedWriter에 저장하였습니다.
• BufferedWriter을 사용하여 저장된 결과를 출력하였습니다.

• VPS함수는 스택을 표현하는 Stack이 비어있으면 VPN인 것으로 증명됩니다.
• StackPush()는 '('와 '['가 들어오면 스택에 push되도록 하였습니다.
• StackPop()은 ')'와 ']'가 들어오면 가장 최근에 스택에 push한 괄호와 짝을 이루면 pop을 진행하고 다르면 VPN이 아닌 것을 알려줍니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Stack<Character> stack = new Stack<Character>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //BufferedWriter를 통해 결과 값 출력
        //------입력 값 저장 및 함수 실행-----------
    	while(true) {
    		String text = br.readLine();
    		if(text.equals("."))	//"."일 때 반복 종료
    			break;
    		for(int i=0;i<text.length();i++) {	//스택 관련 명령
    			stackPush(text.charAt(i));
    			boolean check = stackPop(text.charAt(i));
    			if(!check) {
    				stack.push('!');
    				break;
    			}
    		}
    		bw.write(VPS() + "\n");		//결과 저장
    		stack.clear();
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
	}
    //----------스택 push 함수-----------
	public static void stackPush(char c) {
		if(c=='(' || c=='[')
			stack.push(c);
	}
    //---------스택 pop 함수--------------
	public static boolean stackPop(char c) {
		if(c==')') {
			if(stack.empty() || stack.peek() !='(')
				return false;
			else
				stack.pop();
		}
		if(c==']') {
			if(stack.empty() || stack.peek()!='[')
				return false;
			else
				stack.pop();
		}
		return true;
	}
    //---------VPS 확인 함수------------
	public static String VPS() {
		if(stack.empty())
			return "yes";
		else
			return "no";
	}
}