[프로그래머스] 괄호 회전하기 (JAVA)

링크

https://school.programmers.co.kr/learn/courses/30/lessons/76502?language=java

프로그래머스

 

문제 요약

문자열 s가 올바른 괄호 문자열인지 반환하는 문제

 

올바른 괄호 문자열의 정의는 아래와 같습니다.

• (), [], {}는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다.'

 

제한

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

 

풀이

올바른 괄호 문자열 정의에 따라 소괄호를 기준으로 3가지의 구체적인 예시를 만들면 다음과 같습니다.

1. `()`
2. `(())`
3. `()()`

 

올바른 괄호인지 판단하는 과정은 스택을 이용하면 쉽게 풀 수 있습니다.

1. `(`가 나오면 스택에 push 한다.
2. `)`가 나오면 스택에서 pop 한 문자가 `(` 인지 확인한다.
   1. 스택에서 pop을 하기 전에 일단 스택이 비어있진 않은지도 확인한다.
3. s의 문자를 모두 순회한 후, 스택이 비어있는지 확인한다.
   1. 올바른 괄호라면 스택이 모두 비어있어야 한다.

위 과정을 중괄호, 대괄호에도 똑같이 적용할 수 있습니다.

그리고 s를 왼쪽으로 회전시키면서 이를 매번 수행하면 됩니다.

 

최종 코드 흐름은 다음과 같습니다.

1. x는 0으로 초기화한다.
2. s를 x만큼 왼쪽으로 회전시킨다.
3. s가 올바른 괄호인지 판단한다.
4. (x <s의 길이-1)이라면 x를 1 증가시킨 후, 2~3 과정을 반복한다.

 

여기서 고민해야 할 부분은 “s를 x만큼 왼쪽으로 어떻게 회전할 것인가?”입니다.

왼쪽으로 회전시키면, 문자열 길이는 동일하지만 시작점 인덱스가 하나씩 증가됩니다.

그리고 시작점 인덱스는 x 값과 동일한 것을 알 수 있습니다.

따라서 이러한 공식을 세울 수 있습니다.

• 시작점 인덱스: `x`
• 문자열 속 문자를 순회하는 변수 : `i` (`0`≤`i` <`s의 길이`)
• x만큼 왼쪽으로 회전시킨 s의 특정 문자 인덱스: `(x+i)%(s의 길이)`

 

코드

import java.util.*;
class Solution {
    public int solution(String s) {
        int cnt = 0;
        for(int x=0; x<s.length(); x++){
            if(isValid(s,x)) cnt++;            
        }         
        return cnt;
    }
    
    boolean isValid(String s, int x){
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<s.length(); i++){
            char c = s.charAt((x+i)%s.length());
            if(c=='(' || c=='[' || c=='{'){
                stack.push(c);
            } else{
                if(stack.isEmpty()) return false;
                if(c==')' && stack.pop()!='(') return false;
                if(c==']' && stack.pop()!='[') return false;
                if(c=='}' && stack.pop()!='{') return false;
            }
        }
        return stack.isEmpty();
    }
}

🏷 시간 복잡도

• N: s의 길이
• `isValid()`: O(N)
• solution의 for문: 최대 N번 반복
• 최종 시간 복잡도 = O(N*N)