[240326] 알고리즘 리부트 39일차 - 프로그래머스 괄호 회전하기 자바

스택을 deque로 활용함으로써 자료구조를 양껏 활용한 풀이이다. 다만 값을 빼고 넣는 순서를 헷갈리기 쉽다.

import java.util.*;


class Solution {
    public int solution(String s) {
        
        char[] target = s.toCharArray();
        
        // 기본 문자열 스택에 담아 놓기
        Deque<Character> base = new ArrayDeque<>();
        
        for(int i = 0; i<target.length; i++){
            base.push(target[i]);
        }
        
        int ans = 0;
        
        for(int i = 0; i<target.length; i++){
            // 회전하는 방식
            // 회전 문자 수가 0개 ~ (문자열 길이 -1)이니까 1 이상인 경우에
            // 해당 스택의 가장 밑에 깔려있는 값을 제일 위로 올려줌
            if(i >= 1) base.push(base.pollLast());
            
            // 해당 base 가지고 임시 stk 생성 
            Deque<Character> tmp = new ArrayDeque<>(base);
            
            // 이 stk에 넣으면서 판별하기
            Deque<Character> stk = new ArrayDeque<>();
            
            // 처음부터 닫힌 괄호인지 확인
            boolean impossible = false;
            
            while(!tmp.isEmpty()){
                // 순서대로 판별해야 하는데 가장 밑에 있는 문자가
                // 가장 앞에 있는 수이므로 pollLast();
                char thisLetter = tmp.pollLast();
                
                if(stk.isEmpty()&&((thisLetter == ')')||(thisLetter == '}')||(thisLetter == ']'))) {
                    impossible = true;
                    break;
                }
                
                if((!stk.isEmpty() && stk.peek()=='(' && thisLetter==')')||
                   (!stk.isEmpty() && stk.peek()=='{' && thisLetter=='}')||
                   (!stk.isEmpty() && stk.peek()=='[' && thisLetter==']')) {
                    stk.pop();                    
                }
                
                else {
                    stk.push(thisLetter);
                }
            }  
            // 처음부터 닫힌 괄호라 0개인 경우를 제외하고 카운트
            if(!impossible && stk.isEmpty()) ans++;
            
        }   
        
        return ans;
        
    }
}

두번째는 map을 활용한 풀이이다. 짝이 맞는 괄호를 맵으로 구현해 놓고 짝 판별하는 코드이다. 확실히 코드가 간결하다.

import java.util.*;


class Solution {
    public int solution(String s) {
        
        int ans = 0;
        
        HashMap<Character, Character> map = new HashMap<>();
        
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
        
        int len = s.length();
        s+=s;
        
        A: for(int i = 0; i<len; i++){
            
            Deque<Character> stk = new ArrayDeque<>();
            
            for(int j = i; j<i+len; j++){
                char thisLetter = s.charAt(j);
                
                if(map.containsKey(thisLetter)) stk.push(thisLetter);
                if(!map.containsKey(thisLetter) && stk.isEmpty()) continue A;
                if(!stk.isEmpty() && thisLetter == map.get(stk.peek())) stk.pop();
                
            }
            
            if (stk.isEmpty()) ans++;
            
        }
        
        return ans;
    }
}