알고리즘 풀이 - 프로그래머스(문자열 압축(Lv 2), 문자열)

 

관련글

 

문자열 관련 포스팅은 추후 업데이트

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

비손실 문자열 압축 알고리즘을 통해 주어진 문자열을 압축했을 때, 가장 길이가 짧은 길이를 구하는 문제

 

 

2. 풀이

 

문제 이해를 잘못해서 풀이에 오래 걸렸다.

이 문제는 앞에서부터 문자열을 잘라서 압축하여 표현된 결과값을 구하여 해결하면 된다.

단순 문자열 다루기 문제이다.

 

이 문제가 길지만 쉬운 이유는 다음의 조건이 있기 때문이다.

 

- 중간부터 잘라서 사용할 수는 없다.

예를 들어 아래와 같은 상황을 보자.

예 : abcdbcd 를 보자.
상식적으로 생각하면 3개 단위로 나누어서 표현하면, a2bcd 라고 하면 가장 짧을 것이다.
하지만, a를 무시하고 중간부터 자를 수는 없기 때문에 이것은 의미가 없어서 결국 정답은 abcdbcd가 된다.

 

1개 단위부터 최대 자를 수 있는 단위는 전체 길이의 1/2 이므로 그 단위까지 잘라가며, 전체 길이가 가장 짧은 경우를 구하면 된다.

아래 코드의 주석을 보면서 이해해보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

class Solution {
    public int solution(String s) {
        int answer = compress(s);
        return answer;
    }
    private int compress(String s){
        if(s.length() == 1) return 1;
        int len = s.length();
        int min = Integer.MAX_VALUE;
        
        char[] arr = s.toCharArray();
        
        // 1개 부터 전체 길이의 반까지 잘라서 압축 시도
        for(int i=1; i <= len/2; i++){
            int idx = 0;         // 비교 진행 시작할 Index
            int cnt = 0;         // 동일한 문자열이 이어진 횟수
            String splited = ""; // 압축된 전체 문자열
            String str = "";     // 현재 비교 대상 문자열
            
            // 비교 시작할 Index에서 압축 시도할 크기를 더한 값이 전체 길이보다 작거나 같을 때까지 반복
            while(idx + i <= len){
            
                if(!String.valueOf(arr, idx, i).equals(str)){ // 비교 시 다른 경우
                    if(cnt > 1) splited += cnt;  // 1개 이상 같으면 숫자를 붙인다.
                    splited += str;  // 문자열을 붙이고
                    str = String.valueOf(arr, idx, i);  // 비교 대상 문자열을 갱신
                    cnt = 1; // 횟수를 1로 초기화
                
                } else {     // 비교 시 같은 경우
                    cnt++;   // 횟수 ++
                }
                idx += i;    // 비교 시작할 위치를 변경
            }
            
            // 비교 뒤 남은 문자열을 붙여준다.
            if(cnt > 1) splited += cnt;
            splited += str;
            
            if(idx < len) splited += String.valueOf(arr, idx, arr.length - idx);
            min = Math.min(min, splited.length());
        }
        return min;
    }
}

 

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.