섹션 5. Stack, Queue - 5. 쇠막대기

📌 문제 설명

여러 개의 쇠막대기를 겹쳐 놓고 위에서 레이저를 수직으로 발사하여 자릅니다. 이때 괄호로 구성된 문자열이 쇠막대기와 레이저의 배치를 나타냅니다.

• 쇠막대기의 시작: '('
• 쇠막대기의 끝: ')'
• 레이저: 인접한 '()'

이러한 표현을 바탕으로 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 괄호 표현이 공백 없이 주어집니다 (길이 최대 100,000)

출력

• 잘려진 쇠막대기 조각의 총 개수 출력

---

🔹 예제 입력 & 출력

예제 입력 1

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

 

예제 출력 1

17

 

예제 입력 2

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

 

예제 출력 2

24

---

💡 해결 방법

• Stack을 활용하여 여는 괄호 '('를 저장합니다.
• 닫는 괄호 ')'가 나왔을 때 이전 문자가 '('이면 레이저이므로 stack의 size만큼 조각 수를 추가합니다.
• 그 외의 ')'는 막대의 끝이므로 1개의 조각이 추가됩니다.

---

💻 코드 구현 (Java)

package partStackQueue;

import java.util.Scanner;
import java.util.Stack;

public class Problem5 {
	public int solution(String s) {
		int result=0;
		Stack<Character> stack = new Stack<>();
		for(int i=0; i<s.length(); i++) {
			if(s.charAt(i)=='(') stack.push('(');
			else {
				stack.pop();
				if(s.charAt(i-1)=='(') result+=stack.size(); // 레이저: stack에 남은 '(' 개수만큼 잘림
				else result++; // 막대의 끝: 조각 1개 추가
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Problem5 T = new Problem5();
		Scanner kb = new Scanner(System.in);
		System.out.print(T.solution(kb.next()));
		kb.close();
	}
}

---

📖 코드 설명

if(s.charAt(i)=='(') stack.push('(');

• 여는 괄호는 쇠막대기의 시작 또는 레이저의 시작 → Stack에 저장

stack.pop();
if(s.charAt(i-1)=='(') result+=stack.size();
else result++;

• 닫는 괄호의 경우:
  • 이전 문자가 '('이면 레이저 → Stack 크기만큼 조각 수 추가
  • 이전 문자가 ')'이면 막대기 끝 → 조각 1개 추가

---

⏳ 시간 복잡도 분석

• 문자열 길이 N만큼 한 번 순회 → O(N)
• Stack 연산은 O(1)으로 전체 시간 복잡도는 O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런