[스택] 프로그래머스 괄호회전하기 // 회전하지 말고 뒤에붙여라

https://school.programmers.co.kr/learn/courses/30/lessons/76502?gad_source=1&gad_campaignid=22199869887&gbraid=0AAAAAC_c4nDqT-kGu7HDiWreRKNyvkYUK&gclid=Cj0KCQjw1JjDBhDjARIsABlM2St3rddqiQ5vq_1tewqUOwj4SfVP6m4BAGqsMZ-_YLamLn7pOQO_k5QaAub0EALw_wcB

프로그래머스

* 풀이1

직접회전

[이면 push 아니면 pop

반례 -> }}} 만 오는 경우 true 가 되버림 -> leftCnt로 left의 갯수가 없다면 false 리턴

import java.util.*;

class Solution {
    String rotate(String s){
        return s.substring(1) + s.charAt(0);
    }
    boolean check(String s){
        int leftCnt=0;
        Stack<Character> stk = new Stack<>();
        for(int i=0;i<s.length();++i){
            char cur = s.charAt(i);
            if(s.charAt(i)=='[' || s.charAt(i)=='(' || s.charAt(i)=='{'){
                leftCnt++;
                stk.push(s.charAt(i));
            }
            else if(stk.size()>0 && cur==']' && stk.peek()=='['){
                stk.pop();
            }
            else if(stk.size()>0 && cur==')' && stk.peek()=='('){
                stk.pop();
            }
            else if(stk.size()>0 && cur=='}' && stk.peek()=='{'){
                stk.pop();
            }
        }
        return stk.isEmpty() && leftCnt!=0;
    }
    public int solution(String s) {
        int answer = 0;
        int n=s.length();
        for(int i=0;i<n;++i){
            // System.out.println(s);
            if(check(s)) answer++;
            s=rotate(s);
        }
        return answer;
    }
}

 

* 풀이2

회전하지말고 뒤에 붙여라!

s+=s (문자열 뒤에 자기자신 붙이는법)

Stack대신 ArrayDequeue를 써라

if문대신 map을 사용하라.

반복문에 이름붙이는법.

우측괄호가 in -> stk가 빔 -> false!

import java.util.*;

class Solution {

    public int solution(String s) {
        int answer=0;
        int n=s.length(); //window size
        s+=s; // 회전하지말고 붙여라.
        
        HashMap<Character,Character> m = new HashMap<>();
        m.put(')','(');
        m.put(']','[');
        m.put('}','{');
        
        A:for(int i=0;i<n;++i){ //반복문 바로 break 하는방법
            ArrayDeque<Character> stk = new ArrayDeque<>(); //Stack대신 ArrayDequeue를 사용하라.
            for(int j=i;j<i+n;++j){
                char cur = s.charAt(j);
                if(!m.containsKey(cur)){ // 좌측괄호인경우
                    stk.push(cur);
                }
                else if(stk.isEmpty() || stk.pop()!=m.get(cur)){ //우측괄호} 들어옴 -> 스택이 빔 or 같지않음 -> 무효
                    continue A; //A로 이동
                }
                
            }
            if(stk.isEmpty()) answer++; // else if문에 안걸리고 stk가 빈경우, 올바른 괄호
        }
        
        return answer;
    }
}