[알고리즘]Stack - 쇠막대기

5. 쇠막대기
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램

레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현됩니다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현합니다.
쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현됩니다.
입력) 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어집니다.
출력) 잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력합니다.

 

 

1) '(' 무조건 push, '(' 다음에 ')' 나오면 pop하고 answer += stack size, ')' 다음에 ')' 나오면 pop하고 answer++

import java.util.Scanner;
import java.util.Stack;

public class Main { 
	
	public static int solution(String str) {
		int answer = 0, bar = 0;
		Stack<Character> stack = new Stack<>();
		
		for (int i=0; i<str.length(); i++) {
			if (str.charAt(i)=='(') stack.push('(');
			else { // ')'
				stack.pop();
				if (str.charAt(i-1)=='(') answer += stack.size();
				else answer++; // 막대기의 끝
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str = scanner.next();
		System.out.println(solution(str));
	}
}

 

2) '(' 다음에 '(' 나오면 bar++, '(' 다음에 ')' 나오면 answer+= bar 개수, ')' 다음에 ')' 나오면 bar--,answer++

import java.util.Scanner;
import java.util.Stack;

public class Main {
	
	public static int solution(String str) {
		int answer = 0, bar = 0;
		Stack<Character> stack = new Stack<>();
		
		for (char x : str.toCharArray()) { 
			if (x=='(') {
				if (!stack.isEmpty()) {
					if (stack.peek()=='(') bar++;
				}
			} else { // ')'
				if (stack.peek()=='(') answer += bar;
				else { // ')' // 막대기의 끝
					bar--;
					answer++;
				}
			}
			stack.push(x);
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str = scanner.next();
		System.out.println(solution(str));
	}
}

---

결과

입력
(((()(()()))(())()))(()())

출력
24