SWEA D4 5432 쇠막대기자르기

SWEA D4 5432 쇠막대기자르기

 

 

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl47b6DGMDFAXm&categoryId=AWVl47b6DGMDFAXm&categoryType=CODE&problemTitle=5432&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://tv.naver.com/v/21729205

swexpert academy D4 5432 쇠막대기자르기

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d4;

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

/**
 * @author 은서파
 * @since 2021. 2. 3.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl47b6DGMDFAXm&categoryId=AWVl47b6DGMDFAXm&categoryType=CODE&problemTitle=5432&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
 * @mem 27,296 kb
 * @time 142 ms
 * @caution
 *          [고려사항]
 *          앞에서 부터 여는 괄호가 나올 때 마다 스틱을 증가시키고 닫는 괄호가 나올 때마다 스틱을 감소시킨다.
 *          단 레이저에 의해 닫는다면 스틱의 개수만큼 조각이 증가하고 그냥 닫히면 스틱의 끝이므로 조각은 1만 증가한다.
 *          String의 replaceAll을 이용하면 훨씬 간단히 처리된다. 이때 ()는 정규표현식에서 특수문자이므로 escape 처리 필요
 *          [입력사항]
 *          [출력사항]
 */
public class SWEA_D4_5432_쇠막대기자르기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;

	static int T;

	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));

		T = Integer.parseInt(input.readLine());
		for (int t = 1; t <= T; t++) {
			String line = input.readLine();
			int answer = 0;
			//answer = solve(line);
			//answer = solve2(line);
			answer = solve3(line);
			output.append(String.format("#%d %d\n", t, answer));
		}
		System.out.println(output);
	}
	// 27,296 kb, 142 ms
	private static int solve(String line) {
		int stickCnt = 0;
		int pieces = 0;
		// laser 여부를 판단하기 위해 바로 앞의 정보가 무었이었는지 알 필요가 있다.
		char pre = '\u0000';
		for (int i = 0; i < line.length(); i++) {
			// 여는 괄호는 언제나 stick을 증가시킨다.
			if (line.charAt(i) == '(') {
				stickCnt++;
			}
			// 닫는 괄호는 언제나 stick을 감소시키는데..
			// 만약 레이저라면 stick의 개수만큼 조각이 늘어나고 아니면 그냥 하나의 stick이 끝난다.
			else {
				stickCnt--;
				// 이전 문자가 (였고 현재가 )이면 laser --> stick 만큼 조각 증가
				if (pre == '(') {
					pieces += stickCnt;
				}
				// 아니면 한 조각 끝 --> 조각 하나 증가
				else {
					pieces++;
				}
			}
			pre = line.charAt(i);
		}
		return pieces;
	}
	
	// 47,104 kb, 179 ms
	private static int solve2(String line) {
		int pieces = 0;
		int pipeCnt = 0;
		Stack<Character> stack = new Stack<>();
		
		for(int i=0; i<line.length(); i++) {
			char c = line.charAt(i);
			if(c=='(') {
				pipeCnt++;
			}else {
				pipeCnt--; // 파이프삽입이 아니었거나.. 파이프가 끝나거나
				if(stack.peek()=='(') {// 레이저
					pieces+=pipeCnt;
				}else { // 그냥 끝
					pieces++;
				}
			}
			stack.push(c);
		}
		return pieces;
	}
	


	// 64,028 kb, 241 ms
	private static int solve3(String line) {
		line = line.replaceAll("\\(\\)", ":");
		int stickCnt = 0;
		int pieces = 0;
		for (int i = 0; i < line.length(); i++) {
			char c = line.charAt(i);
			if (c == '(') {
				stickCnt++;
			} else if (c == ')') {
				stickCnt--;
				pieces++;
			} else {
				pieces += stickCnt;
			}
		}

		return pieces;
	}

	private static String src = "2\r\n" +
								"()(((()())(())()))(())\r\n" +
								"(((()(()()))(())()))(()())";
}