[백준] 10799 쇠막대기 자바

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

설명을 위해 앞 부분만 보세요.

저는 처음에 단순히 인덱스로 접근해서 마지막 ' ( '로 돌아갔더니 메모리초과가 나서 stack으로 풀었습니다.

 

일단 stack구조를 활용하는 문제입니다. ' ( ' 모양은 모두 push하고,

갈색으로 빗금친 괄호의 뜻은 ' ) ' 모양이 왔을 때에 이전의 ' ( '를 pop한다는 의미입니다.

 

레이저가 지나가는 빨간선,녹색선의 왼쪽을 기준으로 막대의 갯수를 세는 것이 핵심입니다.

레이저가 지나가면 위의 사진처럼 막대가 조각나고, 그것의 갯수는 stack에 쌓아둔 ' ( '의 갯수입니다. (stack size)

 

보라색처럼 이후에 ' ) '모양이 나오면 하나의 막대가 끝나는 것이기 때문에 단순히 +1을 해주면 됩니다.

주의할 점은 ' ( '을 push할 때에 인덱스 값으로 넣어주어야 아래의 코드처럼 레이저를 구분할 수 있습니다.

 

단순히 풀면 풀리긴 하지만 에러나고, 정답풀이를 보면 이해할 수 있지만 떠올리기는 힘든 문제였다고 생각합니다.

 

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

public class 쇠막대기 {

	static String str;
	static Stack<Character> stk = new Stack<Character>();
	static int sum = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine();

		Stack<Integer> s = new Stack<>();
		for (int x = 0; x < str.length(); x++) {
			char next = str.charAt(x);
			
			if(next == ')' && s.peek() == x-1) {
				s.pop();
				sum+=s.size();
			}
			else if(next == '(')
				s.add(x);
			else if(next == ')') {
				s.pop();
				sum ++;
			}

		}
		System.out.println(sum);
	}

}