[코딩테스트합격자되기-자바편] 문제10. 괄호 회전하기

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

출처 : 프로그래머스 - 괄호 회전하기

 

내용

 

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

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

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

 

 

제약 조건

 

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

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
14:34	15:30	56분

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

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

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

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

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(String s) {
    int answer = 0;
    for (i = 0 s.length()) {
        // 임시로 괄호를 담을 stack 생성 
        // 치환시킬 char array 생성
        for (j = i + 1 ; s.length()) {
            // char array 담기
        }
        // 왼쪽으로 돌리기
        for (j = 0; j < i) {
            // char array 담기
        }
        for (char array) {
            // ] } ) stack에 담기
            // [ { ( 이면 stack에 짝지은 게 top에 있는지 확인하기
        }
        // stack 이 비어있으면 answer++
    }
    return answer;
}

 

 

구현

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = 0;
        for (int i = 0; i < s.length(); i++) {
            // 임시로 괄호를 담을 stack 생성
            Stack<Character> stack = new Stack<>();
            // 치환시킬 char array 생성
            char[] array = new char[s.length()];
            // 왼쪽으로 돌리기
            for (int j = 0; j < s.length(); j++) {
                array[(j + s.length() - 1) % s.length()] = s.charAt(j);
            }
            s = String.valueOf(array);
            for (char a : array) {
                if (a == '[' || a == '{' || a == '(') {
                    stack.add(a);
                } else if (a == ']') {
                    if (!stack.isEmpty() && stack.peek() == '[') {
                        stack.pop();
                    } else {
                        stack.add(a);
                    }
                } else if (a == '}') {
                    if (!stack.isEmpty() && stack.peek() == '{') {
                        stack.pop();
                    } else {
                        stack.add(a);
                    }
                } else if (a == ')') {
                    if (!stack.isEmpty() && stack.peek() == '(') {
                        stack.pop();
                    } else {
                        stack.add(a);
                    }
                }
            }
            // stack 이 비어있으면 answer++
            if (stack.isEmpty()) {
                answer++;
            }
        }
        return answer;
    }
}

 

 

 

복기하기

저자 권장 시간	권장 시간 복잡도
30분	O(N^2)

 

답안과 나의 풀이를 비교해보세요

import java.util.ArrayDeque;
import java.util.HashMap;

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

        int n = s.length();
        s += s;
        int answer = 0;

        A: for (int i = 0; i < n; i++) {
            ArrayDeque<Character> stack = new ArrayDeque<>();
            for (int j = i; j < i + n; j++) {
                char c = s.charAt(j);
                if (!map.containsKey(c)) {
                    stack.push(c);
                }
                else {
                    if(stack.isEmpty() || !stack.pop().equals(map.get(c))) {
                        continue A;
                    }
                }
            }
            if (stack.isEmpty()) {
                answer++;
            }
        }
        return answer;
    }
}

• 회전하는 숫자가 정해져 있다면 문자열을 사이클 횟수만큼 반복하여 붙이는 게 나을 수도 있다.

 

 

요약하기

• map을 사용하여 올바른 괄호인지 판별하는 코드를 좀 더 간결하게 작성할 수 있다.