섹션 5. Stack, Queue - 2. 괄호문자제거

📌 문제 설명

입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고, 남은 문자만 출력하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 줄에 문자열이 주어집니다. (길이 ≤ 100)

출력

• 소괄호 안의 문자를 모두 제거한 나머지 문자열 출력

---

🔹 예제 입력 & 출력

예제 입력 1

(A(BC)D)EF(G(H)(IJ)K)LM(N)

 

예제 출력 1

EFLM

---

💡 해결 방법

• Stack을 활용해 괄호 내부의 문자들을 제거하는 방식
• 문자 하나씩 순회하면서 여는 괄호 (부터 닫는 괄호 )까지 Stack에서 제거
• 괄호 외부의 문자만 Stack에 남게 됨

---

💻 코드 구현 (Java)

package partStackQueue;

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

public class Problem2 {
	public StringBuilder solution(String str) {
		StringBuilder answer = new StringBuilder();
		Stack<Character> stack = new Stack<>();
		
		for(char x: str.toCharArray()) {
			if(x != ')') stack.push(x);
			else {
				while(stack.pop() != '(');
			}
		}
		for(char c : stack) {
			answer.append(c);
		}
		return answer;
	}

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

---

📖 코드 설명

Stack<Character> stack = new Stack<>();

• 문자를 담기 위한 Stack 생성

for(char x: str.toCharArray()) {
	if(x != ')') stack.push(x);
	else {
		while(stack.pop() != '(');
	}
}

• 문자 하나씩 순회하며 닫는 괄호 )가 나오기 전까지 모두 Stack에 push
• 닫는 괄호가 나오면 여는 괄호 (까지 Stack에서 pop하여 괄호 안 문자 제거

for(char c : stack) {
	answer.append(c);
}

• Stack에 남은 괄호 밖 문자들을 결과 문자열로 변환

---

⏳ 시간 복잡도 분석

• 문자열 길이를 N이라 할 때 각 문자에 대해 Stack 연산 수행: O(N)

---

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

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

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