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

1. 문제

---

프로그래머스

2. 풀이 과정

---

• 먼저 올바른 괄호 문자열이 되는 기준부터 이해하고 가야한다
  1. ( ), { }, [ ] 
  2. A가 올바른 괄호일 때 (A), {A}, [A]
  3. A, B가 올바른 괄호일 때 AB
• 즉, 닫힌괄호가 오려면 그 앞에 온 가장 최신의 열린괄호는 그 닫힌괄호와 짝을 이루는 열린괄호여야한다.
• 또한 문자열을 왼쪽으로 회전한다는 말은 ABC -> BCA -> CAB처럼 맨 왼쪽에 있는 문자열이 맨 뒤로 가는 것을 말한다.
• 코드 흐름
  • 문자열 s의 길이만큼 문자열을 회전시켜야 하므로 그만큼 for문을 돌림
  • 그 for문 안에 올바른 괄호인지를 판단하는 로직과 왼쪽으로 회전하는 로직이 들어가야 함

3. 내 코드

---

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer_cnt = 0;
        Stack<Character> stack = new Stack<>();
        
        for(int i = 0; i < s.length(); i++) {
            // 올바른 괄호 문자열인지    
            for(int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                
                if(c == '(' || c == '{' || c == '[') { // 여는 괄호일경우 스택에 푸시
                    stack.push(c);
                } else if(c == ')' || c == '}' || c == ']') { // 닫는 괄호일 경우
                // 스택이 비어있거나 stack의 최신 여는괄호와 짝이 안맞으면 올바른 괄호가 아님
                    if(stack.isEmpty() || (int)stack.peek() / 10 != (int)c / 10) { 
                        break;
                    } else {
                        stack.pop(); 
                    }
                }
                
                if(j == s.length() - 1 && stack.isEmpty()) {
                    answer_cnt++;
                }
            }
            
            stack.clear(); // 스택 초기화 하기
            s = rotateString(s); // 문자 왼쪽으로 회전시키기 
        }
        return answer_cnt;
    }
    
    private String rotateString(String s) {
        return s.substring(1) + s.substring(0, 1);
    }
}

시간복잡도

• O(N^2)

// 스택이 비어있거나 stack의 최신 여는괄호와 짝이 안맞으면 올바른 괄호가 아님
if(stack.isEmpty() || (int)stack.peek() / 10 != (int)c / 10) { 
    break;
} else {
    stack.pop(); 
}

• 괄호의 짝 여부를 판단하는 코드에서 고민이 있었는데 나는 해당 문자의 아스키코드값으로 해결했다.
  • '(': 40  ')': 41
  • '{': 123 '}': 125
  • '[': 91 ']': 93
• 아스키코드값을 10으로 나눈 몫이 같은 점을 이용했다.

4. 다른 정답 코드와 비교

---

[『코딩 테스트 합격자 되기 - 자바편』 해설 코드]

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

class Solution {

    public static int solution(String s) {
        // ❶ 괄호 정보를 저장함. 코드를 간결하게 할 수 있음
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');

        int n = s.length(); // 원본 문자열의 길이 저장
        s += s; // 원본 문자열 뒤에 원본 문자열을 이어 붙여서 2번 나오도록 만들어줌

        int answer = 0;

        // ❷ 확인할 문자열의 시작 인덱스를 0 부터 n 까지 이동
        A:for (int i = 0; i < n; i++) {
            ArrayDeque<Character> stack = new ArrayDeque<>();

            // ❸ i(시작 위치)부터 원본 문자열의 길이인 n개까지 올바른 괄호 문자열인지 확인
            for (int j = i; j < i + n; j++) {
                char c = s.charAt(j);
                // HashMap 안에 해당 key 가 없다면 열리는 괄호임
                if (!map.containsKey(c)) {
                    stack.push(c);
                }
                else {
                    // ❹ 짝이 맞지 않으면 내부 for문은 종료하고 for문 A로 이동
                    if(stack.isEmpty() || !stack.pop().equals(map.get(c)))
                        continue A;
                }
            }

            // ❺ 3에서 continue 되지 않았고, 스택이 비어있으면 올바른 괄호 문자열임
            if (stack.isEmpty())
                answer++;
        }

        return answer;
    }

}

시간복잡도

• O(N^2)

내 코드와 차이점

1.괄호의 짝을 찾아주는 기능을 구현하기 위해 HashMap을 사용했다.

// ❶ 괄호 정보를 저장함. 코드를 간결하게 할 수 있음
HashMap<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');

 

2. 문자열을 회전하기 위해 같은 문자열을 두번 붙여주었다.

int n = s.length(); // 원본 문자열의 길이 저장
s += s; // 원본 문자열 뒤에 원본 문자열을 이어 붙여서 2번 나오도록 만들어줌

5. 피드백

---

• 최신의 데이터를 참조해야할 때는 스택 자료구조를 떠올리자
• 짝을 짓는 부분을 해시맵으로 해결하는 부분은 창의적이고 코드를 깔끔하게 만드는 것 같다.