백준 | 10799 : 쇠막대기 (Java)

문제에 대한 자세한 정보는 백준 | 10799번 : 쇠막대기에서 확인할 수 있다.

풀이

Stack을 사용해서 풀어도 되는 문제지만 사용하지는 않았고 문자가 '(' 인지, ')' 인지에 따라 변수를 증가, 감소시키며 풀이했다.

1. 쇠막대기( '(' ) 개수를 세는 cnt 변수, 조각 개수를 세는 piece 변수를 선언해 0으로 초기화한다.
2. 반복문으로 charAt(i)를 사용해 문자열을 검사한다. 아래는 반복문 과정이다.
3. '(' 이면 cnt값을 1만큼 증가시킨다.
4. ')' 이면 쇠막대기나 레이저가 끝난 것이므로 cnt값을 1만큼 감소시킨다.
   4-1. charAt(i-1)이 ')' 였다면 쇠막대기가 끝난 것이므로 조각이 1개 늘어난다. 따라서 piece값을 1만큼 증가시킨다.
   4-2. 4-1의 경우가 아니라면 charAt(i-1)이 '(' 인 것이고 레이저가 끝난 것이므로 현재 쇠막대기 개수인 cnt값을 piece에 더해준다.
5. piece값을 출력한다.

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String temp = br.readLine();
		int cnt = 0;
		int piece = 0;

		for (int i = 0; i < temp.length(); i++) {			
			if(temp.charAt(i) == '(') {
				cnt++;
			} else { // ')'
				cnt--;
				if(temp.charAt(i - 1) == ')') { // 쇠막대기가 끝남
					piece++;
				} else { // 레이저 끝남
					piece += cnt;
				}
			}
		}

		bw.write(String.valueOf(piece));

		br.close();
		bw.close();
	}
}

메모리, 시간

메모리 : 14080KB
시간 : 104ms

풀이 후

그림을 보면서 직접 조각을 세보면 풀 수 있는 방법이 금방 떠오르는 문제였다.