[백준] 10799: 쇠막대기

비가츄·2022년 8월 1일

stack 백준 알고리즘

문제 설명

문제 링크는 여기를 눌러주세요!

10799번: 쇠막대기

Untitled

위와 같이 괄호 입력이 주어졌을 때, 괄호 두 개 이상 중첩된 경우 쇠막대기가 있다고 가정한다. 이때 중첩이 없는 괄호가 닫힐 때 레이저를 통해 쇠막대기를 절단한다.

문제가 원하는 최종 출력은 입력에 대해 결과적으로 얻을 수 있는 쇠막대기의 개수이다.

접근

처음에는 Stack을 이용해서 여는 괄호는 Stack에 저장, 닫는 괄호가 나올 때 Stack의 길이-1만큼 더해주는 식으로 답을 구하고자 했다.

왜 Stack의 길이 - 1 로 생각했는가?
⇒ 예제를 보면 알 수 있듯이 중첩 없는 괄호의 경우 쇠막대기 절단 역할만 할 뿐, 실질적으로 쇠막대기 개수에 더해지지 않는다. 따라서 닫는 괄호의 짝인 여는 괄호 하나는 빼야 한다고 생각했다.

		int result = 0;
		char[] arr = br.readLine().toCharArray();
		
		for(char c : arr) {
			if(c=='(') stack.add(c);
			else {
				result += stack.size() - 1;
				stack.pop();
			}
		}

작성하고 생각해보니 그냥 stack.pop()을 먼저하면 -1을 할 필요가 없을 것 같아서 아래처럼 변경했다.

		for(char c : arr) {
			if(c=='(') stack.add(c);
			else {
				stack.pop();
				result += stack.size();
			}
		}

이 다음 문제는 쇠막대기 절단 후 끝 부분에 대한 값이 더해지지 않는다는 것이었다. 그리고 이 부분은 정확히 닫는 괄호의 연속되는 개수-1와 같았다.

처음에는 이 값을 구하는데 변수를 통해서 해결하고자 했다. (foreach문을 쓰고 있기 때문에)

		int result = 0;
		char[] arr = br.readLine().toCharArray();
		int end = -1;
		
		for(char c : arr) {
			if(c=='(') {
				stack.add(c);
				if (end>=0) {
					result += end;
					end = -1;
				}
			} else {
				stack.pop();
				result += stack.size();
				end++;
			}
		}

그리고 이 접근은 완전히 틀렸다..

어떤 부분이 틀렸는지 확인하고자 출력문을 추가해보았다.

Untitled

살펴보니 의도와 다르게 닫는 괄호가 연속해서 등장 시 한 번 더 쇠막대기가 짤리는 것같이 값이 들어가는 것 같았다.

코드도 눈에 잘 안 들어와서 디버깅이 힘든 것 같아 index를 이용한 for문 형태로 코드를 수정하였다.

		int result = 0;
		char[] arr = br.readLine().toCharArray();
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i]=='(') stack.add(arr[i]);
			else {
				stack.pop();
				result += stack.size();
				
				while(i+1<arr.length && arr[i+1]==')') {
					result += 1;
					stack.pop();
					i++;
				}
			}
		}

의도대로 동작할 수 있게끔, 닫는 괄호 등장 시 닫는 괄호가 연속되는만큼 result를 더하는 식으로 구현하였다.

소스코드

최종 코드는 다음과 같다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Character> stack = new Stack<>();
		
		int result = 0;
		char[] arr = br.readLine().toCharArray();
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i]=='(') stack.add(arr[i]);
			else {
				stack.pop();
				result += stack.size();
				
				while(i+1<arr.length && arr[i+1]==')') {
					result += 1;
					stack.pop();
					i++;
				}
			}
			
		}

		System.out.print(result);
	}
}