[백준 #9012] 괄호

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

 

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다.

예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

예제 입력 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

 

예제 출력 1

NO
NO
YES
NO
YES
NO

 

예제 입력 2

3
((
))
())(()

 

예제 출력 2

NO
NO
NO

 

해결 코드

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

public class Main {
	//전형적인 스택 활용 문제
	
	public static String isVPS(String[] PS, int length) {
		
		Stack<String> stack = new Stack<>();

		for(int i=0; i<length; i++) {
			if(PS[i].equals("(")) {
				stack.add("(");
			}
			else if(PS[i].equals(")")) {
				if (stack.isEmpty()) return "NO";
				else {
					if(stack.peek().equals(")")) return "NO";
					else stack.pop();
				}
			}
		}
		if(stack.isEmpty()) return "YES";
		else return "NO";
	}
	
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		scanner.nextLine();
		
		StringBuffer sb = new StringBuffer();
		for(int i=0; i<n; i++) {
			String PS = scanner.nextLine();
			int length = PS.length();
			String [] PSArray = PS.split("");
			
			sb.append(isVPS(PSArray, length)).append("\n");
		}
		
		System.out.println(sb);
	}
	
}

 

 

• 괄호 문자열(PS)이 주어질 때, 올바른 괄호 문자열(Valid Parenthesis String, VPS) 인지 판단하는 문제.
• 올바른 괄호 문자열이면 "YES", 아니라면 "NO" 출력.

 

 

 

---

1. 자료구조

• Stack<String>
  • 여는 괄호 ( 를 만나면 스택에 추가.
  • 닫는 괄호 ) 를 만나면 스택의 맨 위 요소(()를 제거 (즉, pop() 수행).
  • 괄호가 짝이 맞지 않거나 닫는 괄호가 먼저 나오면 "NO".
• StringBuffer (출력 최적화)
  • 여러 개의 테스트 케이스를 한 번에 출력하여 성능 최적화.

 

 

 

---

2. 알고리즘 분석

 

1) VPS 검사 (isVPS 함수)

public static String isVPS(String[] PS, int length) {
    Stack<String> stack = new Stack<>();

    for(int i = 0; i < length; i++) {
        if(PS[i].equals("(")) {
            stack.add("(");
        }
        else if(PS[i].equals(")")) {
            if (stack.isEmpty()) return "NO";  // 스택이 비었는데 ')'가 나오면 NO
            else {
                if(stack.peek().equals(")")) return "NO"; // ')'만 남아있는 경우 NO
                else stack.pop(); // 정상적인 경우 '('를 제거
            }
        }
    }
    return stack.isEmpty() ? "YES" : "NO";
}

 

 

• 여는 괄호(() → 스택에 push
• 닫는 괄호())
  • 스택이 비어 있으면 "NO" 반환.
  • 스택의 맨 위가 )이면 "NO".
  • 그렇지 않으면 pop() (올바른 괄호 쌍 제거).
• 마지막에 스택이 비었으면 "YES", 남아있으면 "NO".

시간 복잡도

• 문자열의 길이를 L이라 할 때, 한 번 순회하면서 O(L).
• N개의 테스트 케이스에 대해 O(NL).
  (단, 최악의 경우 L ≈ 50, N ≈ 1,000이므로 충분히 빠름)

 

---

 

2) 입력 및 실행 (main 함수)

public static void main(String args[]) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    scanner.nextLine();
    
    StringBuffer sb = new StringBuffer();
    for(int i = 0; i < n; i++) {
        String PS = scanner.nextLine();
        int length = PS.length();
        String[] PSArray = PS.split(""); // 문자열을 문자 배열로 변환
        
        sb.append(isVPS(PSArray, length)).append("\n");
    }
    
    System.out.println(sb);
}

 

• n개의 테스트 케이스 입력.
• split("")을 사용하여 문자열을 문자 배열(PSArray)로 변환.
• isVPS 함수 호출 후 결과를 StringBuffer에 저장 후 출력.

시간 복잡도

• O(NL), 즉 문자열 길이 L만큼 반복하므로 효율적.

 

 

 

---

3. 개선할 점

 

1)String[] PSArray 사용 없이 char 비교 가능

public static String isVPS(String PS) {
    Stack<Character> stack = new Stack<>();

    for(char ch : PS.toCharArray()) {
        if(ch == '(') stack.push(ch);
        else {
            if (stack.isEmpty()) return "NO";
            stack.pop();
        }
    }
    return stack.isEmpty() ? "YES" : "NO";
}

 

 

•  

 

• split("") 대신 toCharArray() 사용 → 메모리 절약.
• char를 Stack<Character>에 저장하여 비교 (연산 속도 향상).

 

---

 

2) 스택 없이 카운터 활용 (O(N), 공간 절약)

public static String isVPS(String PS) {
    int count = 0;

    for(char ch : PS.toCharArray()) {
        if(ch == '(') count++;
        else {
            if(count == 0) return "NO";
            count--;
        }
    }
    return count == 0 ? "YES" : "NO";
}

 

 

 

 

• 스택을 쓰지 않고 count 변수 사용 → 공간 복잡도 O(1).
• 닫는 괄호())가 먼저 나오면 "NO" 즉시 반환.

 

 

---

4. 결론

✅ 핵심 정리

방법	시간 복잡도	공간 복잡도	특징
스택 사용 (기본 코드)	O(L)	O(L)	코드가 직관적이지만 스택 메모리 사용
스택 사용 (char 배열 최적화)	O(L)	O(L)	split("") 대신 toCharArray() 사용
카운터(count) 활용	O(L)	O(1)	공간 효율적, 스택 없이 동작

 

• 기존 코드에서 스택을 카운터(count)로 대체하면 공간 절약 가능.
• 문자열을 split("") 대신 toCharArray() 사용하면 성능 개선.
• 시간 복잡도는 O(L), 전체적으로 O(NL).

 

 

 

---

카운터를 활용하는 방법은 그리디(Greedy) 알고리즘의 개념을 적용한 것이다.

그리디 알고리즘은 각 단계에서 최적의 선택(현재 최선)을 하면서 전체 문제의 최적해를 찾는 방식이다.

 

이를 카운터 방식과 비교해 보면:

1. 그리디 전략 적용

• 문자열을 왼쪽에서 오른쪽으로 한 번만 확인하면서,
  • 여는 괄호 ( → 카운터 +1 증가
  • 닫는 괄호 ) → 카운터 -1 감소
• 중간에 count < 0이 되면, 더 이상 VPS가 될 가능성이 없으므로 즉시 "NO" 반환.
• 끝까지 탐색 후 count == 0이면 "YES", 아니면 "NO".

🔹 즉, 각 문자를 처리할 때마다 현재 상태에서 최선의 선택을 하는 방식 → 그리디 방식과 동일

 

2. 왜 그리디인가?

그리디 알고리즘이 가능하려면:

1. "현재 선택이 전체 최적해에 영향을 미치지 않아야 함"
   • 현재 count 값이 0 미만이면 더 이상 VPS가 될 수 없음 → 즉시 "NO" 반환 (지역 최적해 선택).
   • 현재까지의 괄호가 올바르다면, 이후의 괄호 조합만 확인하면 됨.
2. "항상 최적의 선택을 보장해야 함"
   • count를 유지하면서 여닫는 괄호 쌍을 맞추는 것은 전체 VPS 검사를 수행하는 최적의 방법.
   • 한 번만 문자열을 스캔하므로 불필요한 연산 없이 O(1) 공간으로 해결.

결론적으로, 현재까지의 정보만 보고 최선의 결정을 내리면서, 최종적으로 올바른 괄호 여부를 판단하므로 그리디적인 방법이다.