[Baekjoon] 10799_쇠막대기

문제(출처: https://www.acmicpc.net/problem/10799)

---

< 쇠막대기 >

 

문제 풀이 

 

Stack을 사용하여 문제를 해결한다.

여는 괄호와 닫힌 괄호가 연달아 있을 때 쇠막대기를 자른다는 점을 활용한다.

 

 my solution (Java)

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

public class _10799_ { // 쇠막대기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		String str = bf.readLine();

		Stack<Character> stack = new Stack<>();
		int result = 0;
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				stack.add('(');
				if (str.charAt(i + 1) != ')') {
					result += 1;
				}
			} else {
				stack.pop();
				if(str.charAt(i-1)!=')') {
					result += stack.size();
				}
			}
		}
		System.out.println(result);
	}
}

변수)
str : 쇠막대기와 레이저 배치를 나타내는 괄호 표현
stack : 잘려진 조각의 개수를 구하기 위한 Stack
result : 잘려진 조각의 총 개수

 

쇠막대기와 레이저 배치를 나타내는 괄호 표현을 입력받는다. 괄호 표현을 탐색하며 다음 과정을 수행한다.

 

1) 여는 괄호라면 stack에 추가한다. 만약 다음이 닫는 괄호가 아니라면 쇠막대기란 뜻이므로 result에 1을 추가한다.

2) 닫는 괄호라면 stack에서 pop 한다. 만약 이전이 닫는 괄호가 아니라면 레이저란 뜻이므로 stack에 있는 쇠막대기를 다 자르므로 result에 stack의 크기만큼 더한다.

 

최종 잘려진 조각의 총 개수인 result를 출력한다.

---

---