[프로그래머스] Lv.2 괄호 회전하기

알고리즘 : 스택

---

문제 설명

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

프로그래머스

 

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

(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
s의 길이는 1 이상 1,000 이하입니다.

---

스택을 사용하는 전형적인 문제다.
처음에 인자로 전달 받는 문자열에 관해 Deque로 저장하였지만,
문자열을 2배 늘려서 인덱스로 인한 접근으로 하는 풀이도 보았다.

문자열을 그대로 두고 모듈러 연산으로 인덱스에 접근한 풀이가 제일 좋다고 생각한다.

나의 풀이

1. ArrayDeque로 인자로 전달 받는 스트링을 저장한다.

• 회전을 구현 시 용이하게 하기 위함

2. 매 회전 회차마다 stack으로 확인 수행

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        // 문자열 저장 Deque
        ArrayDeque<Character> list = new ArrayDeque<>();
        for (char c : s.toCharArray()){
            list.addLast(c);
        }

        // 짝 맞춰놓기 
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');

        int strSize = s.length();
        for (int i = 0;i < strSize;i++){
            ArrayDeque<Character> stack = new ArrayDeque<>();
            boolean isVaild = true;
            for (char target : list){
                if (!map.containsKey(target)) stack.push(target);
                else {
                    if (stack.isEmpty()){
                        isVaild = false;
                        break;
                    }
                    else if (!map.get(target).equals(stack.pop())){
                        isVaild =false ;
                        break;
                    }

                }

            }
            if (isVaild && stack.isEmpty()) answer++;

            char temp = list.poll();
            list.addLast(temp);
        }


        return answer;
    }
}

좋은 풀이

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        Map<Character, Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');

        int strSize = s.length();
        for (int startIdx = 0; startIdx < strSize;startIdx++){
            ArrayDeque<Character> stack = new ArrayDeque<>();
            boolean flag  = true;
            for (int i = startIdx; i < startIdx + strSize; i++ ){
                int accessIdx = i % strSize;
                char target = s.charAt(accessIdx);
                if (!map.containsKey(target)) stack.push(target);
                else {
                    if (stack.isEmpty()){
                        flag = false;
                        break;
                    }
                    else if (!map.get(target).equals(stack.pop())){
                        flag = false;
                        break;
                    }
                }

            }
            if (flag && stack.isEmpty()) answer++;
        }
        return answer;
    }
}