[SWEA] JAVA - 5432.쇠막대기 자르기

처음에 문제를 어떻게 풀것인지에 대해 '오늘 수업에서 스택을 배워서 스택 자료구조를 사용할껏같습니다'라고 생각했다가 반성한 문제입니다. 처음 아이디어가 떠오르지 않아 수업을 듣고나서 이해했습니다.

 

또한 스택을 사용해서 풀어도 되지 않은 문제이고 레이저가 나올때 누적한 쇠막대기값과 나와있는 쇠막대기 개수를 더해나가면 되는 문제였습니다.

 

만약 () 이런 형식의 레이저가 아니고 ')' 만 나왔을때는 쇠막대기가 끝나는 지점이므로 나와있는 쇠막대기 개수인 cnt값을 -1 감소시키고 누적 쇠막대기 값도 +1만 더해주면된다

 

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

//탐욕 기법 Greedy 알고리즘
//번뜩이는 아이디어가 좀 필요하다 연습을 통해 극복하자
/**
 * sum : 잘려진 조각의 총개수 누적
 * cnt : 나와있는 쇠막대기 개수
 * 
 * () 레이저	: sum += cnt
 * (		: cnt++
 * )		: sum++, cnt--
 */
public class SWEA_5432 {
	//cnt는 현재 쇳조각개수로 -1 +1 이렇게 변화한다 <- 닫힌괄호면 cnt-1 sum+1
	//sum 은 누적 쇠조각
	//레이저가 나오면 sum+=cnt
	static char[] arr;
	static Stack<Character> stack;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= TC; testCase++) {
			String s = br.readLine(); // ()()()() 이런 문자열
			s = s.replace("()", "v");
			//replace해도 string은 원본 배열이 바뀌지않는다
			
			int sum = 0; // 잘려진 조각의 총개수 누적
			int cnt = 0; // 나와있는 쇠막대기 개수
			//(((v)))(v)v () => v
			for (int i = 0; i < s.length(); i++) {
				if(s.charAt(i) == 'v') { // v 레이저
					sum += cnt; // 쇠막대기만큼 누적
				}else if(s.charAt(i) == '(') { // 시작괄호
					cnt++; // 쇠막대기 추가
				}else { // 닫는 괄호
					sum++; //쇠막대기 1개 마감됨, 개수 추가
					cnt--; // 쇠막대기 개수 1개 줄어듦
				}
			}
			sb.append("#").append(testCase).append(" ").append(sum).append("\n");			
		}
		System.out.print(sb);
	}

}