[프로그래머스] 괄호 회전하기 - 코드 개선!

0️⃣ 문제 링크

프로그래머스

SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

school.programmers.co.kr

1️⃣ 문제 설명

괄호로 이루어진 문자열 s가 주어진다.
문자열을 왼쪽으로 회전시켰을 때, 올바른 괄호 문자열이 되는 경우의 수를 구하는 문제이다.

• 사용할 수 있는 괄호 종류: (), [], {}
• 회전 횟수는 문자열 길이만큼 가능
• 올바른 괄호 문자열의 개수를 반환

2️⃣ 문제 접근 방식

• 문자열 회전
  • 문자열을 실제로 회전시키지 않고 똑같은 문자열을 연결해 사용
• 올바른 괄호 문자열 판별
  • Deque<Character>를 스택처럼 사용
  • 여는 괄호라면 push
  • 닫는 괄호라면
    • 스택이 비어 있으면 실패
    • top과 짝이 맞지 않으면 실패
    • 이 외의 경우는 poll하고 진행

시간 복잡도 : O(N²) → (N ≤ 1000 이므로 완전탐색 가능)
공간 복잡도 : O(N) → (스택 최대 크기)

3️⃣ 전체 코드

import java.util.*;

class Solution {
    static String ss;
    public int solution(String s) {
        int answer = 0;
        ss = s + s;
        for (int i = 0; i < s.length(); i++) {
            if (check(i)) answer++;
        }
        
        return answer;
    }
    
    static public boolean check(int x) {
        Deque<Character> dq = new ArrayDeque<>();
        for (int i = x; i < x + ss.length() / 2; i++) {
            char c = ss.charAt(i);
            if (c == '{' || c == '[' || c == '(') {
                dq.offerLast(c);
            } else {
                if (dq.isEmpty()) return false;
                char top = dq.peekLast();
                if ((top == '{' && c == '}') || (top == '[' && c == ']') || (top == '(' && c == ')')) {
                    dq.pollLast();
                } else {
                    return false;
                }
            }
        }
        if (!dq.isEmpty()) return false;
        return true;
    }
}

4️⃣ 개선된 코드

• 문자열 회전
  • (start + i) % n 인덱싱을 사용해 회전 효과 구현
  • 불필요한 문자열 복사를 제거하여 공간 사용 최소화
• 최적화
  • 문자열 길이가 홀수면 애초에 불가능 → 즉시 종료
  • 회전 후 첫 문자가 닫는 괄호면 검사 생략
  • Deque를 매번 객체 생성하지 않고 clear()로 재사용
    (매번 new ArrayDeque<>() → GC 부담)
• 코드 개선
  • peekLast() 호출 없애기 → 한 번만 pop하고 비교
  • 괄호 매칭 함수 분리 → isMatch 함수

import java.util.*;

class Solution {

    static Deque<Character> stack = new ArrayDeque<>();

    public int solution(String s) {
        int n = s.length();
        if (n % 2 == 1) return 0; // 홀수 길이는 불가능

        int answer = 0;

        for (int start = 0; start < n; start++) {
            char first = s.charAt(start);
            // 닫는 괄호로 시작하면 바로 실패
            if (first == ')' || first == ']' || first == '}') continue;

            if (check(s, start, n)) answer++;
        }
        return answer;
    }

    static boolean check(String s, int start, int n) {
        stack.clear();

        for (int i = 0; i < n; i++) {
            char c = s.charAt((start + i) % n);

            if (c == '(' || c == '[' || c == '{') {
                stack.offerLast(c);
            } else {
                if (stack.isEmpty()) return false;

                char top = stack.pollLast();
                if (!isMatch(top, c)) return false;
            }
        }
        return stack.isEmpty();
    }

    static boolean isMatch(char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '[' && close == ']') ||
               (open == '{' && close == '}');
    }
}

5️⃣ 회고 및 배운점

동일한 알고리즘임에도 불구하고, 객체 생성 최소화와 불필요한 연산 제거를 통해 실행 시간을 약 26.7% 단축 할 수 있었다.
완전탐색도 조건만 맞으면 충분히 좋은 선택이고, N이 작다면 억지로 복잡한 알고리즘을 쓰지 않아도 된다는 것을 다시 한 번 깨달았다.
문자열을 새로 만들기(복사)보다 인덱싱으로 처리하는 습관을 가져야겠다.