프로그래머스 - 문자열 압축 [Java]

이 문제는 스택을 이용해서 풀었다.

 

1부터 s 길이 - 1 까지의 부분 문자열 길이를 정하고, 그 부분 문자열에 대한 압축 연산을 수행하여 길이를 찾아내는 방식이다.

입력 s의 길이가 최대 1,000 이므로, O(n^2) 이하 알고리즘까지도 가능하다.

 

한 가지 주의할 점은 압축 후 마지막에 길이를 계산할 때, 10 이상의 count를 가진 경우 10은 두 자리 수이므로 2를 result에 더해줘야 한다. 이를 위해 String.valueOf() 를 통해 String으로 변환 후 length를 더해주는 것으로 정답을 구했다.=

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

class Solution {
    final Stack<Node> st = new Stack<Node>();
    
    public int solution(String s) {
        int answer = s.length();
        
        for (int cnt = 1; cnt <= s.length() - 1; cnt++) {
            answer = Math.min(answer, compress(s, cnt));
        }
        
        return answer;
    }
    
    int compress(final String s, final int cnt) {
        for (int i = 0; i < s.length(); i += cnt) {
            if (i + cnt - 1 < s.length()) {
                final String substr = subString(s, i, i + cnt - 1);
                
                operation(substr);
                continue;
            }
            
            final String substr = subString(s, i, s.length() - 1);
            
            st.add(new Node(substr, 1));
        }
        
        int result = 0;
        
        while (!st.isEmpty()) {
            final Node node = st.pop();
            
            if (node.count == 1) {
                result += node.substr.length();
            } else {
                result += node.substr.length();
                result += String.valueOf(node.count).length();
            }
        }
        
        return result;
    }
    
    void operation(final String substr) {
        if (st.isEmpty()) {
            st.add(new Node(substr, 1));
            
            return;
        }
        final Node node = st.peek();
                    
        if (node.substr.equals(substr)) {
            st.pop();
            st.add(new Node(node.substr, node.count + 1));
            
            return;
        }
        
        st.add(new Node(substr, 1));
    }
    
    String subString(final String s, final int start, final int end) {
        StringBuilder sb = new StringBuilder();
        
        for (int i = start; i <= end; i++) {
            final char c = s.charAt(i);
            
            sb.append(c);
        }
        
        return sb.toString();
    }
    
    static class Node {
        String substr;
        int count;
        
        Node (String substr, int count) {
            this.substr = substr;
            this.count = count;
        }
    }
}