괄호 회전하기 (자바)

김재현·2023년 12월 19일
0

알고리즘 풀이

목록 보기
59/90

문제

오답 코드

public int solution(String s) {  //오답
        int answer = 0;

        for (int j=0;j<s.length();j++) {

            int index1 = 0;
            int index2 = 0;
            int index3 = 0;

            for (int i = 0; i < s.length(); i++) {
                    if ((s.charAt(i) == ')') && index1 == 0) { index1++; break;}
                    if ((s.charAt(i) == '}') && index2 == 0) { index2++; break;}
                    if ((s.charAt(i) == ']') && index3 == 0) { index3++; break;}

                    if (s.charAt(i) == '(') index1++;
                    if (s.charAt(i) == '{') index2++;
                    if (s.charAt(i) == '[') index3++;

                    if (s.charAt(i) == ')') index1--;
                    if (s.charAt(i) == '}') index2--;
                    if (s.charAt(i) == ']') index3--;
            }

            if (index1==0 && index2==0 && index3==0) answer++;

            s=s.substring(1)+s.charAt(0);
        }

        return answer;
    }

처음엔 index로 풀려고 시도했다.
닫히는 괄호로 시작되면 그 문자열은 불가능한 문자열이기때문에 바로 break 했다.
그 뒤 열리는 괄호에 대해 index를 올려준 뒤, 닫히는 괄호가 있으면 index를 낮추고 index가 모두 0이라면 answer를 1 올렸다.

하지만 실패케이스가 하나 나왔다.
생각해보니 "({)}" 와 같은 문자열은 오답이지만 정답으로 처리되었던 것이다.

index를 활용해서 바꿀 수도 있겠지만, stack을 연습하기 위해 정석적인 풀이로 바꿔서 풀었다.

정답 코드

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = 0;

        for (int j=0;j<s.length();j++) {

            Stack<Character> stack = new Stack<>();

            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);

                if (stack.isEmpty()) {
                    stack.push(c);
                } else if (stack.peek() == '(' && c == ')') {
                    stack.pop();
                } else if (stack.peek() == '{' && c == '}') {
                    stack.pop();
                } else if (stack.peek() == '[' && c == ']') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
            if (stack.isEmpty()) answer++;

            s=s.substring(1)+s.charAt(0);
        }

        return answer;
    }
}

데이터를 후입선출(LIFO, Last In, First Out)의 구조로 관리하는 자료구조를 구현한 클래스인 'Stack'을 이용하면 간단히 해결되는 문제였다.

profile
I live in Seoul, Korea, Handsome

0개의 댓글