[Algorithm] 문자열 압축

프로그래머스 문제

https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

풀이

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = s.length();
        
        // 단위가 1부터 s.length() 까지
        for (int len = 1; len < s.length(); len++) {
            // 단위별 압축된 문자열 저장
            String comp = "";
            // 시작할 때 문자열
            String pre = s.substring(0, len);
            // 카운트, 숫자를 넣으면 aa -> 2a로 숫자칸 확보하고 시작
            int cnt = 1;
            // 스트링 len만큼씩 자르면서 
            for (int i = len; i < s.length(); i += len) {
                // len만큼의 문자열 호출
                String sub = "";
                for (int j = i; j < i + len; j++) {
                    if (j < s.length()) sub += s.charAt(j);
                }
                // pre와 sub 비교 같다면, cnt++, 다르다면 pre에 새로운 pre를 부여함
                if (pre.equals(sub)) cnt++;
                else {
                    comp += (cnt >= 2) ? cnt+pre : pre;
                    sub = "";
                    for (int j = i; j < i + len; j++) {
                        if (j < s.length()) sub += s.charAt(j);
                    }
                    pre = sub;
                    cnt = 1;
                }
            }
            // 남은 문자열
            comp += (cnt >= 2) ? cnt + pre : pre;
            answer = Math.min(answer, comp.length());
        }
        
        return answer;
    }
}

 

 

substring으로 푼 풀이

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = s.length();  
        for (int len = 1; len < s.length(); len++) {
            int cnt = 1;
            String comp = "";
            String prev = s.substring(0, len);
            for (int i = len; i < s.length(); i += len) {
                String now = "";
                if (i + len < s.length()) {
                    now = s.substring(i, i+len);
                } else {
                    now = s.substring(i);
                }
                
                if (prev.equals(now)) {
                  cnt++;
                }
                else {
                    comp += (cnt >= 2) ? cnt+prev : prev;
                    prev = now;
                    cnt = 1;
                }
            }
            comp += (cnt >= 2) ? cnt + prev : prev;
            answer = Math.min(answer, comp.length());
        }

        return answer;
    }
}