[SWEA] 쇠막대기 자르기

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다.

 

✍🏻풀이

스택을 사용해서 풀었다!

스택에는 String str의 인덱스를 저장해둔다.

 

( 를 만날 때는 stack.add를, )를 만날 때는 이 괄호가 레이저인지, 쇠막대기인지 구분해서 처리해주면 된다.

String str에 쇠막대기와 레이저의 배치를 입력받고, for문으로 str에 접근한다.

쇠막대기인지, 레이저인지 구별하는 방법은 str.charAt(i)가 ')'일 때, stack.peek()가 i - 1인지 확인하고, stack.peek()가 i - 1 이라면, 레이저라는 뜻이고, 아니면 쇠막대기라는 뜻이다. (레이저를 의미하는 괄호쌍은 인접하기 때문이다.)

레이저일 때는 먼저, stack.pop()을 한 후, stack.size()만큼 cnt에 더해주고,

쇠막대기일 때는 cnt에 1을 더해주면 되는데, 이유는 다음과 같다.

 

파란색 레이저일 때, 옆 괄호에서 파란색으로 체크한 부분들만 stack에 들어가있는 상태이고,

초록색 레이저일 때도, 옆 괄호에서 초록색으로 체크한 부분들만 stack에 들어가있는 상태이다.

빨간색 레이저일 때도, 옆 괄호에서 빨간색으로 체크한 부분들만 stack에 들어가있는 상태이다.

레이저가 나갈 때, 잘리는 막대기를 보면, 각각 색깔로 체크한 부분들이 괄호에서 체크한 부분들과 개수가 같은걸 알 수 있다.

 

노란색 ')'를 보면, 막대기가 끝났다는 표시이므로, 그 부분에 잘린 막대기 (1개)를 cnt에 더해줘야 한다.

이걸 이제 코드로 구현하면 된다..!

 

설명하기 어렵당..

 

코드

package swea;

// 쇠막대기 자르기 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl47b6DGMDFAXm )

import java.util.*;
import java.io.*;

public class SWEA_5432 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		Stack<Integer> stack;
		String str;
		T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			stack = new Stack<>();
			str = br.readLine();
			
			// solve
			stack.add(0);
			int cnt = 0;
			
			for (int i = 1; i < str.length(); i++) {
				if (str.charAt(i) == '(') {
					stack.add(i);
				}
				else {
					if (stack.peek() == (i - 1)) { // 레이저
						// 레이저일 때는 stack.size()만큼 cnt에 더해준다.
						stack.pop();
						cnt += stack.size();
					}
					else { // 쇠막대기
						// 쇠막대기가 끝날 때는, cnt에 1을 더해준다.
						cnt += 1;
						stack.pop();
					}
				}
			}
			
			bw.write("#" + tc + " " + cnt);
			bw.newLine();
		}
		
		bw.flush();
		bw.close();
	}
}