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

https://school.programmers.co.kr/learn/courses/30/lessons/76502

 

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

(), [], {} 는 모두 올바른 괄호 문자열입니다.

만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다. 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

문제 이해

주어진 s문자열을 왼쪽부터 x (0 ≤ x < (s의 길이)) 만큼 잘라 오른쪽으로 이어붙인 새로운 문자열을 만드는 과정을 반복할 때, 올바른 괄호 문자열이 되는 횟수를 구하는 문제.

각 괄호 '('와 ')', '{'와 '}', '['와']'의 개수가 서로 같지 않다면 회전해도 올바른 괄호 문자열이 되지 않을테니, 회전하기 이전에 괄호 쌍의 개수가 서로 같은지 확인하고자 함.

 

알게된 점

`isValid()` 메소드에서 `HashMap <String, Integer> mapper = new HashMap<>()` 으로 선언했으니, primitive type이 아니므로 `==`이 아닌 `equals` 혹은 `compareTo`로 비교를 해주어야한다. 

그러나, primitive type으로 생각하여 `==` 비교 연산으로 코드를 작성했었고, 제출하게되면 1~11번 테스트케이스에서 실패를 보게되었다. 처음에는 원인을 알지 못했다.

원인을 찾아보기위한 과정 중 하나로 `"`를 `'`로 바꿔보기도 했었다. mapper.getOrDefault(')',0) 과 같이 ""가 아닌 ''로 해주면 또, 통과가 되는 것이 아닌가? 그래서 엥? 하고 정말 뭘까 싶었는데, `'`로 묶었을 때 되었던 것은 모두 0의 값이 나와 isValid가 true값을 반환하여 회전코드가 실행되었기 때문에 테스트케이스가 통과된 것이었다.

 

1. reference type은 ==로 비교하게되면 주소값을 비교하게 되므로, equals, compareTo를 이용하여 값 비교를 해주자.

2. Integer인 reference type이라도, -127~128은 캐싱을 이용하여 ==로 값 비교가 되기는 한다. 그러나 그 이후의 값은 안되는 것 같다.

 

코드

import java.io.*;
import java.util.*;

class Solution {
    
    public int solution(String s) {
        int answer = 0;
    
        if(isValid(s)){
            for(int i=0; i<s.length(); ++i)
                answer += countValidString(s, i);
        }
        
        return answer;
    }
    public int countValidString(String s, int len){
        Stack<Character> st = new Stack<>();
        String str = s.substring(len)+s.substring(0, len);
        for(int i=0; i<str.length(); ++i){
            char cur = str.charAt(i);
            if(st.isEmpty() && ((cur==')') || (cur ==']') || (cur == '}'))) return 0;
            if((cur=='(') || (cur =='[') || (cur == '{')){
                st.add(cur);
            }else{
                char top = st.peek();
                if(top == '('  && cur == ')'){
                    st.pop();
                }else if(top == '{' && cur == '}'){
                    st.pop();
                }else if(top == '[' && cur == ']'){
                    st.pop();
                }else{
                    st.add(cur);
                }
            }
        }
        
        if(st.isEmpty()) return 1;
        return 0;
    }
    public boolean isValid(String s){
        HashMap<String, Integer> mapper = new HashMap<>();
        String[] str = s.split("");
        
        for(int i=0; i<str.length; ++i){
            mapper.put(str[i], mapper.getOrDefault(str[i], 0)+1);
        }
        
        return ((mapper.getOrDefault("(", 0).equals(mapper.getOrDefault(")", 0))) && (mapper.getOrDefault('[', 0).equals(mapper.getOrDefault(']', 0))) && (mapper.getOrDefault('{', 0).equals(mapper.getOrDefault('}', 0))));
    }
}