[프로그래머스] 자바(Java) - 올바른 괄호

🧩 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

💡 알고리즘 설계 및 코드

1. 일단 첫번째로 이 문제를 보고 스택을 사용해야겠다고 판단한 이유는
   • 닫힌 괄호 `)` 가 열린 괄호 `(` 와 짝을 맞추는데, 단순히 아무 열린 괄호와 맞추는 것이 아니라 가장 가까운 열린 괄호와 짝이 맞춰져야 하기 때문입니다.
   • 이러한 특징은 스택의 LIFO 구조와 비슷하고 즉, 최근에 삽입된 데이터를 대상으로 연산을 수행해야 하기 때문에 스택을 사용하는 것이 적합하다고 판단하였습니다.
2. 열린 괄호를 만나면 스택에 추가합니다.
3. 닫힌 괄호가 나온다면 스택에서 열린 괄호를 제거합니다. (짝기 맞춰졌기 때문에)
4. 스택이 비어있는지 확인하여 모든 열린 괄호가 닫힌 괄호와 짝을 이루었는지 판단합니다.

import java.util.*;

class Solution {
    boolean solution(String s) {
        char[] ch = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for(char c : ch) {
            if(c == '(') {
                stack.push(c);
            } else {
                if(stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

• 문자열을 문자 배열로 변환
  • 입력 문자열 s를 `toCharArray()` 메서드를 사용하여 문자 배열 ch로 변환합니다.
• 스택 초기화
  • 괄호의 짝을 맞추기 위해 빈 스택 `Stack`을 선언합니다.
• 문자 배열을 순회하면서 괄호 처리
  • 현재 문자가 열린 괄호이면 스택에 `push()` 합니다.
  • 현재 문자가 닫힌 괄호라면 스택이 비어있는지 확인합니다.
    • 예를 들어, 문자열 `(()))` 에서 앞의 `(())` 는 짝이 맞아 상쇄되고, 맨 마지막 닫힌 괄호 `)` 를 만났을 때 스택이 비어 있으면, 올바른 짝이 없다는 의미이기 때문에 false 를 반환해줍니다.
    • 그렇지 않으면 스택에서 최근 요소를 `pop()` 하여 짝을 맞춥니다.
• 스택이 비어 있으면 모든 괄호가 올바르게 짝을 맞춘 것이므로 `isEmpty()` 를 사용하여 true 를 반환하고, 그렇지 않으면 false 를 반환합니다.

 

⏱️ 시간 복잡도

이 문제에서 주어진 제안 사항에 따르면 문자열 s의 길이가 100,000 이하의 자연수로 제한됩니다.

N의 가용 범위가 100,000 이므로 최대 `O(NlogN)` 시간 복잡도까지 활용할 수 있습니다.

• 문자열 순회
  • for 루프를 통해 문자열의 각 문자를 한 번씩 순회합니다.
  • 문자열의 길이를 N이라 하면, 이 순회의 시간 복잡도는 O(N)입니다.
• 스택 연산
  • 스택에 문자를 push 하거나 pop 하는 연산은 각각 O(1) 의 시간 복잡도를 가집니다.
  • 각 호출은 상수 시간이므로 전체 루프 내에서의 스택 시간 복잡도는 O(N) * O(1) = O(N) 입니다.
• isEmpty()
  • isEmpty() 의 시간 복잡도는 O(1) 입니다.
• 즉, 이 코드의 전체 시간 복잡도는 O(N) 입니다.