Programmers | Level 2 | 괄호 회전하기

Programmers | Level 2 | 괄호 회전하기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Stack

Description

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

1. (), [], {} 는 모두 올바른 괄호 문자열입니다.
2. 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
3. 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < s의 길이) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

Constraints

• s의 길이는 1 이상 1,000 이하입니다.

Examples

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

Solutions

• ⏳ TC: O(n^2)
• 💾 SC: O(n)

import java.util.*;

class Solution {
    public int solution(String s) {
        StringBuilder sb = new StringBuilder(s);
        int validCount = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // 문자열을 왼쪽으로 회전
            sb.append(sb.charAt(0));  // 첫 번째 문자를 문자열의 끝에 추가
            sb.deleteCharAt(0);       // 첫 번째 문자를 삭제
            
            // 올바른 괄호 문자열인지 확인
            if (isValidParentheses(sb.toString())) {
                validCount++; 
            }
        }
        
        return validCount;
    }
    
    private boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<>(); 
        
        for (char c : s.toCharArray()) {
            if (stack.isEmpty()) {
                stack.push(c);
            } else if (stack.peek() == '[') {
                checkAndUpdateStack(stack, c, ']');
            } else if (stack.peek() == '{') {
                checkAndUpdateStack(stack, c, '}');
            } else if (stack.peek() == '(') {
                checkAndUpdateStack(stack, c, ')');
            } else {
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
    
    private void checkAndUpdateStack(Stack<Character> stack, char currentChar, char expectedChar) {
        if (currentChar == expectedChar) {
            stack.pop();
        } else {
            stack.push(currentChar);
        }
    }
}

Approaches

이 문제는 문자열을 왼쪽으로 회전시키면서 올바른 괄호 문자열인지 확인하는 문제입니다. 이를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

• 문자열 회전:
  • 주어진 문자열 s를 StringBuilder를 사용하여 왼쪽으로 한 칸씩 회전시킵니다.
  • 문자열을 왼쪽으로 회전시키기 위해 먼저 append() 메서드를 사용하여 첫 번째 문자를 문자열의 끝에 추가합니다. 그런 다음 deleteCharAt() 메서드를 사용하여 첫 번째 문자를 삭제합니다. 이를 통해 문자열을 왼쪽으로 한 칸 회전시킬 수 있습니다.
  • 예를 들어, s가 ""일 때 첫 번째 문자를 끝에 추가하고 첫 번째 문자를 삭제하면 "]()["가 됩니다.
• 올바른 괄호 문자열 검사:
  • 회전된 문자열이 올바른 괄호 문자열인지 확인하기 위해 스택을 사용합니다.
  • 문자열의 각 문자를 순회하며 여는 괄호는 스택에 푸시하고, 닫는 괄호는 스택의 최상위 요소와 비교하여 맞는 쌍인지 확인합니다.
  • 쌍이 맞지 않거나 스택이 비어있는 경우 올바른 괄호 문자열이 아닙니다.
  • 예를 들어, 문자열 ""을 순회하며 스택을 사용하여 여는 괄호를 푸시하고 닫는 괄호와 비교하여 올바른 괄호 문자열인지 확인합니다.
• 결과 반환:
  • 모든 회전된 문자열을 검사한 후 올바른 괄호 문자열인 경우의 수를 반환합니다.

이 알고리즘의 시간 복잡도는 문자열의 길이가 n일 때, O(n^2)입니다. 각 회전된 문자열을 검사하는 데 O(n)이 소요되며, 이를 n번 반복하기 때문입니다. 공간 복잡도는 스택을 사용하기 때문에 O(n)입니다. 이는 주어진 문제를 효율적으로 해결하는 데 충분합니다.