[프로그래머스] Lv.2 괄호 회전하기 (Python / Java)

 

코딩테스트 연습 - 괄호 회전하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명

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

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

제한사항

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

 

입출력 예

 

---

문제 풀이

1. 닫는 괄호를 열린 괄호와 매칭시키는 맵(또는 딕셔너리) 생성
2. 회전된 문자열 생성
3. 회전된 문자열을 차례대로 탐색
4. 만약 현재 문자가 열린 괄호 (예: {, (, [) 라면 이를 스택에 넣기
5. 만약 현재 문자가 닫힌 괄호 (예: }, ), ]) 라면, 스택의 가장 위에 있는 괄호를 확인
   • 스택이 비어있다면, 이는 올바르지 않은 괄호 (닫힌 괄호에 해당하는 열린 괄호 없음)
   • 스택의 최상단 괄호가 현재 닫힌 괄호와 짝을 이루는 열린 괄호라면, 이 괄호를 스택에서 제거
   • 스택의 최상단 괄호가 현재 닫힌 괄호와 짝을 이루지 않는다면, 이는 올바르지 않은 괄호 (예: '({)' )
6. 모든 문자 탐색한 후, 스택이 비어있다면 괄호가 올바르게 사용되어있다는 것을 의미
     

[Python]

def solution(s):

    mapping = {")":"(", "]":"[" ,"}":"{"}
    answer = 0

    for i in range(len(s)):
        a = s[i:] + s[:i]

        stack = []
        check = 1

        for char in a:
            if char in mapping:
                if stack and stack[-1] == mapping[char]:
                    stack.pop()
                else:
                    check = 0
                    break
            else:
                stack.append(char)
        if check and not stack:
            answer +=1

    return answer

 

[Java]

import java.util.*;

class Solution {
    public int solution(String s) {

        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')','(');
        mapping.put(']','[');
        mapping.put('}','{');

        int answer = 0;

        for(int i = 0; i < s.length(); i++) {
            String a = s.substring(i) + s.substring(0,i);

            Stack<Character> stack = new Stack<>();
            boolean check = true;

            for (char c : a.toCharArray()) {
                if (mapping.containsKey(c)) {
                    if(!stack.empty() && stack.peek() == mapping.get(c)) {
                        stack.pop();
                    } else {
                        check = false;
                        break;
                    }
                } else {
                    stack.push(c);
                }
            }
            if (check && stack.empty()) 
                answer++;            
        }
        return answer;
    }
}