(백준, BOJ 10799) 철봉(java)

https://www.acmicpc.net/problem/10799

10799번: 철봉

일부 철봉을 레이저로 절단하려고합니다.

효율적인 작업을 위해 철봉을 아래에서 위로 쌓고 레이저를 위에서 수직으로 발사하여 철봉을 자릅니다.

철봉과 레이저

www.acmicpc.net

문제

일부 철봉을 레이저로 절단하려고합니다.

효율적인 작업을 위해 철봉을 아래에서 위로 쌓고 레이저를 위에서 수직으로 발사하여 철봉을 자릅니다.

철봉과 레이저 배치는 다음 조건을 충족합니다.

철봉은 자신보다 긴 철봉 위에만 둘 수 있다.

– 철봉을 다른 철봉 위에 놓을 때는 완전히 포함되도록 하고 엔드포인트는 겹치지 않도록 둔다.
각각의 철봉을 절단하는 레이저는 적어도 하나 존재한다.
레이저는 어떤 철봉의 양 끝점과 겹치지 않는다.

아래 그림은 위의 조건을 충족하는 예를 보여줍니다.

수평으로 그려진 두꺼운 실선은 철봉이고, 점은 레이저의 위치, 수직으로 그려진 점선의 화살표는 레이저의 발사 방향이다.

이러한 레이저와 철봉의 배치는 다음과 같이 괄호를 사용하여 왼쪽부터 순서대로 표현할 수 있다.

레이저는 열린 괄호와 닫힌 괄호의 인접한 쌍 “()”로 표시됩니다.

또한 모든 “()”는 반드시 레이저를 나타냅니다.
철봉의 좌단은 오픈 괄호 ‘(‘로, 우단은 닫는 괄호 ‘)’로 표시된다.

위 예제의 괄호 표현은 그림 위에 제공됩니다.

철봉은 레이저에 의해 일부 단편으로 잘리고, 위의 예에서는 최상위 2개의 철봉이 각각 3개와 2개의 단편으로 잘리고, 이와 같이 주어진 철봉은 총 17개로 잘립니다.

철봉과 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘린 철봉 조각의 총수를 구하는 프로그램을 작성합니다.

입력

한 줄에 철봉과 레이저의 배치를 나타내는 괄호 표현이 공백없이 제공됩니다.

괄호 문자의 수는 최대 100,000입니다.

출력

잘린 부분의 총수를 나타내는 정수를 1행에 출력합니다.

728×90

입력 예 1

()(((()())(())()))(())

출력 예 1

샘플 입력 2

(((()(()()))(())()))(()())

출력 예 2

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String() args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char() bracket = br.readLine().toCharArray();
		
		int rodCount = 0; // 현재 위치에서 쌓인 쇠막대기 개수
		int result = 0; // 잘려진 쇠막대기 조각의 총 개수
		
		for (int i = 0; i < bracket.length; i++) {
			if(bracket(i) == '(') { // 여는 괄호가 나왔을 때, 쇠막대기의 왼쪽 끝인지, 레이저인지 확인
				if(bracket(i + 1) == ')') { // 바로 닫는 괄호가 나왔다면 레이저
					result += rodCount; // 현재 위치에서 쌓인 쇠막대기 개수만큼 잘려진 쇠막대기 조각이 나온다
					i++;
				}
				else rodCount++;
			}
			else { // 닫는 괄호가 나왔다면 쇠막대기의 오른쪽 끝이므로 쇠막대기 조각 수를 하나 더해준다
				result++;
				rodCount--;
			}
		}
		
		// 출력
		System.out.println(result);
	}

}

(백준, BOJ 10799) 철봉(java)

인기글

문제

입력

출력

입력 예 1

출력 예 1

샘플 입력 2

출력 예 2