프로그래머스 Lv.2 - 60057 문자열 압축

프로그래머스 Lv.2 - 60057 문자열 압축 문제 풀이

 

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

 

문제의 자세한 내용은 해당 링크를 통해 확인 : 문제 링크

 

풀이 코드

class Solution {
    public int solution(String s) {
    	// 사용할 변수 선언
        int answer = s.length();	// 입력 문자열의 길이로 초기화
        StringBuilder sb = new StringBuilder();	// 최종 문자열을 담는 변수
        
        // 로직 시작
        for(int size = 1; size <= s.length() / 2; size++) {	// 입력 문자열의 길이에 절반까지 반복
            String compareString = s.substring(0, size);	// 비교할 문자열 지정
            String nextString = "";	// 다음 문자열을 저장할 변수 선언
            int count = 1;	// 카운트 변수 선언, 비교할 문자열 지정 후 다음 문자열부터 확인하기 때문에 1로 초기화
            
            for(int i = size; i < s.length(); i+=size) {	// 비교 문자열 다음부터 시작하여 입력 문자열 마지막까지 반복
                if(s.length() > i + size)	// i + size가 입력 문자열보다 작으면
                    nextString = s.substring(i, i + size);	// substring(int, int)를 사용해서 다음 문자열을 갖고오고
                else	// 입력 문자열보다 크거나 같으면
                    nextString = s.substring(i);	// substring(int)를 사용해서 다음 문자열을 갖고온다. 이렇게 나눈 이유는 substring(int, int)의 동작 방식 때문

                if(compareString.equals(nextString))	// 동일한 문자열이면
                    count += 1;	// 카운트 증가
                else {	// 동일한 문자열이 아니라면
                    if(count > 1)	// 카운트가 1보다 크면
                        sb.append(count);	// 최종 문자열에 카운트를 추가하고
                    sb.append(compareString);	// 최종 문자열에 비교하던 문자열을 추가
                    count = 1;	// 카운트를 1로 초기화
                    compareString = nextString;	// 비교 문자열을 다음 문자열로 변경
                }
            }
            // 최종 문자열에 추가 안된 내용을 추가
            if(count > 1)
                sb.append(count);
            sb.append(compareString);
            
            if(sb.length() < answer) // 만약 최종 문자열의 길이가 더 작다면 
                answer = sb.length();	// answer에 최종 문자열의 길이를 대입
            sb.delete(0, sb.length());	// 최종 문자열을 담고있던 sb의 내용을 초기화
        }
        return answer;	// 최종 결과 반환
    }
}

 

문제 해결 전략

이라 쓰고 문제를 보고서 어떻게 풀면 될까?에 대한 생각을 정리한 항목

예전 비슷한 문자열 압축 문제를 풀었을 적이 있는데 해당 문제는 좀 더 간단한 문제로써 1개의 문자에 대한 압축만을 하는 문제였기에 stack을 만들어서 동일한 문자라면 stack에 계속 넣고, 다른 문자가 등장하면 현재 stack의 사이즈 + stack에 저장된 문자를 최종 문자열에 넣은 후 stack을 비운 후 다음 문자를 넣어 반복하여 해결하였었다.

이후 해당 문제를 풀었던 사람들끼리 풀이를 공유했었는데 문자를 기록하는 게 아닌 문자의 카운트를 기록하여 푼 사람이 있었고, 더 효율적인 풀이라고 생각되어 기억에 남아있었다.

그러한 상태에서 해당 문제를 풀게 되어 기억에 남았던 방법을 사용해 풀었다.

 

문자열을 압축하는 로직은 비교 문자열과 다음에 나올 문자열을 비교하여 동일하면 카운트를 증가시키고 다음 문자열 비교로 넘어간다. 다른 문자열이 나온 경우, 현재 카운트가 2 이상이라면 카운트와 문자열을 최종 문자열에 추가, 카운트가 1인 경우라면 문자열만 최종 문자열에 추가한다. 이후 비교 문자열을 다음 문자열로 변경하고 위 과정을 반복하여 최종 문자열을 만들어내어 해당 문자열의 길이를 확인하여 더 작은 길이를 저장한다.

이때, 비교 문자열의 길이가 1부터 최대 입력 문자열의 절반(절반을 넘어가는 비교 문자열은 이미 압축이 불가능하기 때문)인 경우 중 가장 압축이 잘 된 문자열을 찾아야 하니 해당 로직 내에서 위 비교 로직을 작성하여 해결하였다.

 

코드의 각 라인에 주석으로 의미를 설명해 두었으므로 천천히 읽어본다면 이해가 될 것이라고 생각됩니다.

---

코드를 업로드해 둔 깃 허브