섹션 5. Stack, Queue - 1. 올바른 괄호

📌 문제 설명

괄호로 이루어진 문자열이 주어질 때, 괄호가 "올바른 구조"인지 판단하는 문제입니다.

• 괄호가 열리면 (, 닫히면 )입니다.
• 올바른 괄호란 닫는 괄호가 항상 여는 괄호보다 뒤에 오며 전체적으로 짝이 맞는 경우를 의미합니다.
• 예: (()())는 올바르며, (()나 ())(는 올바르지 않습니다.

---

📝 입력 & 출력

입력

• 한 줄에 괄호 문자열이 주어집니다. (길이 ≤ 30)

출력

• 올바른 괄호이면 YES, 아니면 NO를 출력합니다.

---

🔹 예제 입력 & 출력

예제 입력 1

(()(()))(()

 

예제 출력 1

NO

 

---

💡 해결 방법

• Stack 자료구조를 활용합니다.
• 여는 괄호 (는 스택에 push합니다.
• 닫는 괄호 )가 나오면 스택에서 pop합니다.
  • 이때 스택이 비어 있으면 짝이 맞지 않으므로 "NO"를 반환합니다.
• 반복이 끝난 후에도 스택에 괄호가 남아 있다면 짝이 남아 있는 것이므로 "NO"를 반환합니다.
• 모든 검사를 통과하면 "YES"를 반환합니다.

---

💻 코드 구현 (Java)

package partStackQueue;

import java.util.*;

public class Problem1 {
	public String solution(String str) {
		String answer = "YES";
		Stack<Character> stack = new Stack<>();

		for(char x: str.toCharArray()) {
			if(x == '(') stack.push(x);
			else {
				if(stack.isEmpty()) return "NO";
				stack.pop();
			}
		}

		if(!stack.isEmpty()) return "NO";
		return answer;
	}

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

---

📖 코드 설명

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

• 문자를 담을 스택을 선언합니다.

if(x == '(') stack.push(x);

• 여는 괄호 (이면 스택에 push합니다.

else {
	if(stack.isEmpty()) return "NO";
	stack.pop();
}

• 닫는 괄호 )이면 스택이 비었는지 확인합니다.
• 비어있으면 올바르지 않은 괄호이므로 즉시 NO 반환
• 아니라면 짝이 맞는 괄호이므로 pop으로 제거

if(!stack.isEmpty()) return "NO";

• 반복이 끝난 후 스택이 비어있지 않다면 짝이 맞지 않은 괄호가 남은 것이므로 NO

---

⏳ 시간 복잡도 분석

• 문자열 길이를 N이라 할 때, 각 문자에 대해 한 번씩만 처리
• push/pop 연산 모두 O(1) 이므로
• 총 시간 복잡도: O(N)

---

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

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

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