[백준] 단계별로 풀어보기(단계:18,스택,JAVA)9012번, 괄호

문제 링크

9012번: 괄호

 

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을 진행하도록 하는 문제입니다.

그래서 저는 ArrayList를 사용하여 스택에 형태를 구현하였습니다.

ArrayList는 자료를 저장하였을 때에 인덱스가 1씩 늘어나기 때문에 가장 최근에 들어간 자료에 인덱스는 ArrayList에 크기 - 1를 가지는 인덱스입니다.

그래서 문자값이 ')'일 때 pop이 되도록 구현할 때 ArrayList에 값을 제거하는 인덱스를 ArrayList.size() - 1로 하였습니다.

'('일 때에는 리스트에 자료를 추가하는 ArrayList.add() 명령어를 사용하여 구현하였습니다.

마지막으로 '('가 나오지 않았는데도 ')'가 먼저 나왔다는 것은 VPS가 아닌 문자열입니다.

그래서 '('가 나오지 않았다는 것은 스택에 아무것도 들어있지 않은 것으로 ArrayList.size()==0일 때입니다.

')'가 나왔으며 ArrayList.size()==0 이면 자동적으로 VPS를 만족하지 않는 것으로 반복문을 break를 사용하여 중단하였습니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 받은 문자열을 String.CharAt()을 사용하여 어떤 문자인지 확인하였습니다.
• '('을 받으면 push, ')'을 받으면 pop을 진행하였습니다.
• 스택이 비어있을 때 ')'을 받으면 VPS이 아닌 것으로 반복을 중단하도록 하였습니다.
• 받은 문자열이 VPS인지 확인하는 함수 VPS()을 만들었습니다.
• 함수 결과값을 BufferedWriter에 저장하였습니다.
• BufferedWriter을 사용하여 저장된 결과를 출력하였습니다.

• VPS함수는 스택을 표현하는 ArrayList의 크기가 0이면 VPN인 것으로 증명됩니다.
• 괄호가 모두 짝을 지으면 스택에는 들어오는 값들이 pop이 진행되기 때문입니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static List<Integer> list = new ArrayList<Integer>();
	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를 통해 결과 값 출력
        //----------입력값 저장-----
    	int index = Integer.parseInt(br.readLine());
    	for(int i=0;i<index;i++) {
        	String text = br.readLine();
        	for(int j=0;j<text.length();j++) {
        		if(text.charAt(j)=='(')		//입력값이 '('일 때 push
        			list.add(1);
        		else if(text.charAt(j)==')') {
                //입력값이 ')'일 때 스택이 비어있으면 VPN 아닌 것 확정 반복 중단
        			if(list.size()==0) {
        				list.add(1);
        				break;
        			}
        			else	//입력값이 ')'일 때 pop
            			list.remove(list.size()-1);
        		}
        	}

        	bw.write(VPS() + "\n");
        	list.clear();
    	}
    	bw.flush();
    	bw.close();
    	br.close();
	}
    //문자열 VPS 맞는지 확인하는 함수
	public static String VPS() {
		if(list.size()==0)
			return "YES";
		else
			return "NO";
	}
}