백준 4949번 균형잡힌 세상(Java, Stack)

문제 설명

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

괄호 ()와 []로 구성된 문장에서 괄호의 짝이 올바르게 맞는지를 판단하는 문제이다.

각 줄마다 하나의 문장이 주어지고, 문장의 마지막은 마침표 .로 끝난다. 이 문장들에 대해 모든 괄호 쌍이 올바르게 열리고 닫히는지 검사해야 한다.

입력은 여러 줄로 주어지며, 마침표만 있는 한 줄(.)이 입력되면 프로그램을 종료한다. 이 줄은 판단 대상이 아니다.

괄호 외의 문자들은 판단에 영향을 주지 않는다.

입력 예시

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

 

출력 예시

yes
yes
no
no
no
yes
yes

---

전체 코드

import java.util.*;

public class Main {
	public String solution(String s) {
		String answer = "yes";
		
		Stack<Character> stack = new Stack<>();
		
		for(char c: s.toCharArray()) {
			if(c=='(' || c=='[') stack.push(c);
			else if(c==')') {
				if(stack.isEmpty() || stack.pop()!='(') return "no";
			} else if(c==']') {
				if(stack.isEmpty() || stack.pop()!='[') return "no";
			}
		}
		if(!stack.isEmpty()) answer = "no";
		
		return answer;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		while(true) {
			String s = sc.nextLine();
			if(s.equals(".")) break;
			else System.out.println(T.solution(s));
		}
		sc.close();
	}
}

---

코드 설명

solution(String s)

• Stack<Character> stack을 사용하여 괄호의 짝을 검사한다.
• 여는 괄호 ( 또는 [가 나오면 스택에 push한다.
• 닫는 괄호 ) 또는 ]가 나오면 스택이 비어 있거나 짝이 맞지 않으면 바로 "no"를 반환한다.
• 반복문 종료 후 스택이 비어 있지 않다면 "no"를 반환한다.
• 모든 괄호가 정상적으로 열리고 닫혔다면 "yes"를 반환한다.

main(String[] args)

• 여러 줄의 문장을 Scanner로 입력받는다.
• 각 줄을 solution() 함수에 전달하여 결과를 출력한다.
• "." 한 줄이 입력되면 종료한다. (출력하지 않음)

---

시간 복잡도 분석

• 한 줄의 문장을 검사할 때 사용하는 반복문은 s.length()만큼 순회한다.
• 각 문자의 처리에는 O(1)의 시간이 걸리므로, 한 줄당 시간 복잡도는 O(n)이다.
• 입력 줄이 총 m줄일 때 전체 시간 복잡도는 O(m * n)이다.
  • m: 입력 줄 수
  • n: 각 줄의 평균 길이