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

코딩테스트 연습 - 괄호 회전하기

문제 이해하기

• 일단, 올바른 괄호 문자열 : 짝이 맞는 것 _ 스택에서 짝이 맞는 것
• 회전 : 한 칸씩 왼쪽에서 빼내서 오른쪽에 붙이는 것.

주어진 s 에 대해, 한 바퀴 돌리려면 최대 1000 개의 경우가 나온다.

이 때 하나의 경우에 대해 매 번 스택을 사용해서 올바른 괄호문자열인지 확인 한다면

총 O(n^2) 이 나오는데 n 이 1000이므로 할만한 듯 하다.

마음에 안 드는 코드..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	public static String gs; // 주어진 문자열
	public static int start, end; // 회전 큐를 만들기 위해
	public static LinkedList<Character> stack = new LinkedList<>();
	public static Map<Character, Character> closeParenthesis = new HashMap<>();

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;

	public static void setUp() throws IOException {

	}

	public static int solution(String s) {
		int ans = 0;
		int len = s.length();
		gs = s;
		start = 0;
		end = len - 1;
		closeParenthesis.put(')', '(');
		closeParenthesis.put('}', '{');
		closeParenthesis.put(']', '[');

		for (int i = 0; i < len; i++) {
			if (isCorrect())
				ans++;
			start++;
			end = (end + 1) % len;
		}
		return ans;
	}
	public static boolean isCorrectPair(Character cur, Character top){
		return closeParenthesis.get(cur) == top;
	}
	public static boolean isCorrect() {
		// s 부터 시작하여 짝을 맞춘다
		stack.clear();
		int curIdx = start;
		while (true) {
			Character cur = gs.charAt(curIdx);
			// 현재 글자가 },],) 인 경우
			if (closeParenthesis.containsKey(cur)) {
				if (stack.isEmpty())
					return false;
				// stack 의 탑에 있는 것과 쌍이 맞는지 확인
				if ( isCorrectPair(cur, stack.getLast()))
					stack.pollLast();
				else
					return false;
			} else
				stack.add(cur);
			// 종료 조건 확인
			if (curIdx == end)
				break;
			curIdx = (curIdx + 1) % gs.length();
		}
		// 종료한 이흐 스택에 남아있는게 있을 경우
		if (!stack.isEmpty())
			return false;
		return true;

	}

	public static void main(String[] args) throws IOException {
		int solution = solution(new String("[](){}"));
		System.out.println(solution);
	}
}

개인적으로 가독성 하나는 최고인 코드

import java.util.Stack;

class Solution {
    private final Stack<Character> stack = new Stack<>();

        public int solution(String s) {
            int answer = 0;
            StringBuilder stringBuilder = new StringBuilder(s);

            for (int i = 0; i < s.length(); i++) {
                stringBuilder.append(stringBuilder.charAt(0));
                stringBuilder.deleteCharAt(0);
                if (correctParenthesis(stringBuilder.toString().toCharArray()))
                    answer++;
            }
            return answer;
        }

        private boolean correctParenthesis(char[] s) {
            for (char c : s) {
                if (!(check(c, '(', ')') && check(c, '[', ']') && check(c, '{', '}')))
                    return false;
            }
            return stack.isEmpty();
        }

        private boolean check(char c, char a, char b) {
            if (c == a)
                stack.push(a);
            else if (c == b)
                if (!stack.isEmpty() && stack.peek() == a) stack.pop(); else return false;
            return true;
        }
}