lango

찍먹? 부먹?
난 부먹 개발자.

4 minute read




문제 풀이

이번 괄호 회전하기 문제는 괄호를 검증하는 것이 가장 주요하다고 볼 수 있다.
그런데, 그냥 하나의 소괄호 ()만 검증하는 것이 아니라 중괄호 {}와 대괄호 [] 까지 올바른 괄호대로 포함되어 있는지를 확인해야 한다.


아이디어 도출

  • 먼저 주어진 괄호 문자열을 왼쪽으로 한 문자씩 문자열 길이만큼 회전시킨다.
    • 문자열의 길이와 반복문 인덱스를 활용하여 문자열을 회전시킨다.
  • 왼쪽으로 한 문자씩 회전시킨 문자열마다 올바른 괄호 문자열인지를 검증한다.
  • 주어진 문자열을 회전시켜서 만들어진 문자열마다 올바른 괄호 문자열인지를 세어서 반환하면 된다.


아이디어는 이외로 단순하다. 바로 코드를 작성해보자.

문자열 회전시키기

1
2
3

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

먼저 주어진 문자열 s를 가지고 왼쪽으로 한 문자씩 회전시키기 위해서 substring() 메소드를 사용한다.
s의 길이만큼 반복하며 현재 인덱스에서 문자열 길이만큼 자른 뒤, 0번째부터 현재 인덱스까지 자른다면, 왼쪽으로 하나씩 회전된 문자열을 만들 수 있게 된다.

예를 들어 (){}[] 라는 예제를 보면 ){}[](로 회전하기 위해 ){}[]와 (를 합해서 만들 수 있다.

괄호 검증하기

이제 앞에서 주어진 문자열을 왼쪽으로 회전시킨 문자열을 구했으니 회전되는 문자열마다 올바른 괄호 문자열인지 확인하면 된다.

1
2
3
4

for(int i=0; i<s.length(); i++) {
    String rotate = s.substring(i, s.length()) + s.substring(0, i);
    if(isBracket(rotate)) answer++;
}

isBracket이라는 메소드를 만들어 문자열의 괄호 여부를 boolean으로 받아와 answer를 카운트하도록 구현하였다.

잘못된 괄호 검증

사실 Stack을 사용하지 않고 Map을 활용해서 괄호를 검증할 수 있을 줄로 알아서, 이를 토대로 괄호 검증 함수를 구현하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public static boolean isBracket(String str) {
    HashMap<Character, Integer> bracket_map = new HashMap<>();
    bracket_map.put('(', 0);
    bracket_map.put('[', 0);
    bracket_map.put('{', 0);
    for(char ch : str.toCharArray()) {
        switch(ch) {
            case '(':
                bracket_map.put('(', bracket_map.getOrDefault('(', 0)+1);
                break;
            case '{':
                bracket_map.put('{', bracket_map.getOrDefault('{', 0)+1);
                break;
            case '[':
                bracket_map.put('[', bracket_map.getOrDefault('[', 0)+1);
                break;
            case ')':
                if(bracket_map.get('(') == 0) return false;
                bracket_map.put('(', bracket_map.getOrDefault('(', 0)-1);
                break;
            case '}':
                if(bracket_map.get('{') == 0) return false;
                bracket_map.put('{', bracket_map.getOrDefault('{', 0)-1);
                break;
            case ']':
                if(bracket_map.get('[') == 0) return false;
                bracket_map.put('[', bracket_map.getOrDefault('[', 0)-1);
                break;
            default:
                break;
        }
    }
    int small = bracket_map.get('(');
    int medium = bracket_map.get('{');
    int big = bracket_map.get('[');
    return (small == 0) && (medium == 0) && (big == 0);
}

HashMap에 (, {, [를 key로 값은 빈도수로 삽입해서 열린 괄호가 나올 때는 해당 키의 값을 1씩 증가시키고 닫힌 괄호가 나왔을 때는 해당 키의 값을 1씩 감소시켰다.

그리고 Map에 존재하는 (, {, [ key에 대한 값들이 모두 0이라면 열린 괄호와 닫힌 괄호의 짝이 잘 맞으니 true를 반환하게 된다.

해당 메소드를 추가하여 테스트 해보니 정상적으로 예제 테스트케이스들이 통과하였고, 제출을 하였으나 테스트 케이스 14번에서 실패하게 되었다.
이유를 살펴보니, 고려하지 못한 검증 조건이 있다는 것을 깨달았다.

자료구조를 Stack으로 수정

고려히지 못한 검증 조건은 주어진 문자열이 올바른 괄호 문자열이냐는 것이다.
예를 들어 ({)} 라는 예제를 보면 (와 { 모두 열린 괄호와 닫힌 괄호가 한 쌍씩 존재하지만, 올바른 위치에 배치되어 있지 않다.

열린 괄호 (가 들어갔으면 닫힌 괄호 )가 나왔을 때 (가 나와야 하는데, 내가 짠 Map을 활용한 로직에는 짝은 맞출 수 있으나 올바른 배치로 이루어진 문자열인지에 대한 검증은 하지 못하고 있었던 것이다. 결국 Map으로는 이를 구현하기가 어렵다고 느껴져 자료구조를 Stack으로 수정하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Stack<Character> stack = new Stack<>();
for (char c : str.toCharArray()) {
    switch (c) {
        case '(': case '{': case '[':
            stack.push(c);
            break;
        case ')':
            if (stack.isEmpty() || stack.pop() != '(') return false;
            break;
        case '}':
            if (stack.isEmpty() || stack.pop() != '{') return false;
            break;
        case ']':
            if (stack.isEmpty() || stack.pop() != '[') return false;
            break;
    }
}
return stack.isEmpty();

Stack으로 괄호 문자열 검증하는 것은 이전에도 많이 해보아서 굉장히 쉽게 구현해낼 수 있었다.
간단하게 정리하자면 소괄호, 중괄호, 대괄호의 열린 괄호가 나온다면 스택에 삽입하고 닫힌 괄호가 나올 때는 스택의 맨 위의 괄호와 일치하는 괄호인지를 확인하면 된다.

이렇게 고친 코드를 제출하니 정상적으로 14번 테스트케이스까지 모든 테스트케이스를 정상적으로 통과하였다.



작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

import java.util.*;

class Solution {

    public int solution(String s) {
        int answer = 0;
        for(int i=0; i<s.length(); i++) {
            String rotate = s.substring(i, s.length()) + s.substring(0, i);
            if(isBracket(rotate)) answer++;
        }
        System.out.println(answer);
        return answer;
    }

    public static boolean isBracket(String str) {
        Stack<Character> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            switch (c) {
                case '(': case '{': case '[':
                    stack.push(c);
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') return false;
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') return false;
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') return false;
                    break;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args){
        Solution sol = new Solution();
        
        // String s = "[](){}";
        // String s = "}]()[{";
        // String s = "{{{}";
        // String s = "(){{))";
        // String s = "(){{]]";
        String s = "{(})";
        
        sol.solution(s);
    }
}

회고

  • 문자열을 회전시키기 위해 substring() 메소드를 적절히 활용할 수 있었다.
  • Stack을 사용하지않고 Map으로도 올바른 괄호 문자열 검증을 할 수 있을 줄 알았지만 마땅히 아이디어가 떠오르지 않아 Stack을 자료구조로 사용하였다.

You may also enjoy