프로그래머스 - 문자열 압축(Java, 2020 카카오)

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

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

풀이

전체 문자열 길이가 1000 밖에 안되기에 O(N^2)로 풀어도 상관없음

주어진 조건을 따라서 구현하기

 

• 문자열을 길이 기준(i)을 1<= i < length 까지 반복한다.
• 문자열을 자를 기준(j)는 0<= j<=length/j 까지 반복한다.
• 현재 기준 문자열(now)과 비교할 다음 문자열(comp)을 비교해서 같으면 cnt 증가
• 만약 다를 경우 cnt 길이에 따라 문자열을 처리해준 뒤 cnt를 1로 초기화
• 그리고 끝까지 같을 경우를 대비하기 위해 비교 for 문(j)가 끝난 다음 cnt에 따라 값을 갱신해준다.
• 최소값으로 비교하여 결과값을 출력한다.

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        if(s.length() == 1) return 1;
        // 문자열 기준 1~length 까지
        for(int i=1; i<s.length() ; i++){
            String now = ""; String comp = "";
            String temp = "";
            int cnt = 1;
            
            // j 기준 단위 0부터 length/i 단위까지
            // 나누어 떨어지지않을때 끝까지 계산해주려면 <=
            for(int j= 0; j<=s.length()/i;j++){
                int from = i*j; int to = i*(j+1);
                // 값 넘을 시 보정
                if(to > s.length()) to = s.length();

                // 기준점 변경
                now = comp;
                comp = s.substring(from, to);

                // 비교
                if(now.equals(comp)) cnt++;
                else{
                    if(cnt>1) temp += String.valueOf(cnt);
                    temp += now; 
                    cnt = 1; // 개수 초기화
                }
            }
            // 남은값 처리
            if(cnt>1) temp += String.valueOf(cnt);
            temp += comp; 
            // 갱신
            answer = Math.min(temp.length(), answer);
        }
        
        return answer;
    }
}