알고리즘 #0007

• 문제 링크: 바로가기 (클릭)

I. 문제 상황

1. 초기 코드 작성

• 주어진 문제에 따르면, 문자열을 회전시키면서 여는 괄호와 닫는 괄호가 모두 올바르게 위치하는 경우의 수를 구해야 한다.

---

• 닫는 괄호가 들어오면 그게 상응하는 여는 괄호를 제거하는 방식으로 구현하는 것이 적합해 보이므로 Stack 자료구조를 사용하고자 한다.
• ) 문자 차례에서 Stack 자료구조의 top에 있는 문자가 (일 경우 ( 이 문자를 pop()시키는 방식으로 구현하였다.
• 아래의 [코드 1]처럼 코드를 작성한다.

---

• [코드 1] 처음 작성한 코드 답안

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isCorrect(s)) {
                answer++;
            }
            s = rotate(s);
        }
        return answer;
    }
    private boolean isCorrect(String s) {
        int count = -1;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
                count++;
            } else {
                char top = ' ';
                if (ch == ')') {
                    top = '(';
                } else if (ch == ']') {
                    top = '[';
                } else if (ch == '}') {
                    top = '{';
                }
                if (!stack.isEmpty() && top == stack.peek()) {
                    stack.pop();
                }
            }
        }
        if (count == -1) {
            return false;
        }
        return stack.isEmpty()? true: false;
    }
    private String rotate(String s) {
        return s.substring(1, s.length()) + s.substring(0, 1);
    }
}

2. 실행 결과

• 모든 테스트 케이스에서 정상적으로 실행되었다.
• [결과 1]