BOJ. 10799번. 쇠막대기

 

  쇠막대기 문제는 전형적인 스택을 활용한 문제이다. 짝이 맞을 경우에, 끄트머리 부분을 추가해 주면 간단하게 풀이할 수 있다.  java언어를 사용하면서 stack 라이브러리를 처음 사용해 보았다.

www.acmicpc.net/problem/10799

10799번: 쇠막대기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack; // 스택 라이브러리 사용할 때  import

public class Main {

	public static void main(String[] args) throws Exception {
		
		// data input
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String[] bracket = bf.readLine().split("");
		
		// Stack 라이브러리로 선언
		// java에서 stack 함수: push(), pop(), peek():반환만, isEmpty(), size()
		Stack<String> st = new Stack<String>();
		int ans = 0;
		
		for(int i=0; i<bracket.length; i++) {
			String cur = bracket[i];
			if(cur.equals("(")) {
				st.push(cur);
			}else { 				   // cur = )
				String bef = bracket[i-1];
				if(bef.equals("(")) {  // 전( + )
					st.pop();
					ans += st.size();
				}else {                // 전) + )
					st.pop();
					ans += 1;  // 끄트머리 +1
				}
			}
		}

		System.out.println(ans);
	}
}

아래는 라이브러리를 사용하지 않고, 간단한 스택을 구현하여 풀어보았다. (스택을 구현한 부분을 제외하면 동일하다)

import java.io.BufferedReader;
import java.io.InputStreamReader;

class MyStack {
	// 문자 stack
		String[] map = new String[100];
		int top = -1;
//		int size = 0;
		
//	 	push
		void push(String data) {
//			size++;
			top++;
			map[top] = data;
		}
		
//		pop
		String pop() {
			return top == -1 ? null : map[top--];
		}
		
//		size
		int size() {
			return top+1;
		}
		
//		isEmpty
		boolean isEmpty() {
			return top == -1 ? true : false;
		}
		
//		peek
		String peek() {
			return top == -1 ? null : map[top];
		}
}

public class Day1IronBar {

	public static void main(String[] args) throws Exception {
		
		// data input
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String[] bracket = bf.readLine().split("");
		
		MyStack st = new MyStack();
		int ans = 0;
		
		for(int i=0; i<bracket.length; i++) {
			String cur = bracket[i];
			if(cur.equals("(")){
				st.push(cur);
			}else{
				String bef = bracket[i-1];
				if(bef.equals("(")){ //  ( + )
					st.pop();
					ans += st.size();
				}else {				 //  ) + )
					st.pop();
					ans++;
				}
			}
		}

		System.out.println(ans);
	}
}