catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | 문자열 압축

jin@catsriding.com
Oct 11, 2024
Published byJin
999
프로그래머스 | Level 2 | 문자열 압축

Programmers | Level 2 | 문자열 압축

Problems

󰧭 Description

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

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

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

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

 Constraints

  • s의 길이는 1 이상 1,000 이하입니다.
  • s는 알파벳 소문자로만 이루어져 있습니다.

󰦕 Examples

sresult
"aabbaccc"7
"ababcdcdababcdcd"9
"abcabcdede"8
"abcabcabcabcdededededede"14
"xababcdcdababcdcd"17

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    public int solution(String s) {
        int result = s.length();  // 초기값: 원본 문자열의 길이
        
        // 문자열을 1개 단위부터 절반 길이까지 자르며 압축 시도
        for (int i = 1; i <= s.length() / 2; i++) {
            StringBuilder sb = new StringBuilder();  // 압축된 문자열 저장
            String prev = s.substring(0, i);  // 첫 번째 단위 문자열
            int count = 1;  // 반복된 단위 문자열의 개수
            
            // i 단위로 문자열 압축 시작
            for (int j = i; j < s.length(); j += i) {
                String next = i + j > s.length() ? s.substring(j) : s.substring(j, i + j);  // 현재 단위와 비교할 다음 단위
                
                // 같은 단위 문자열이 반복되는 경우 카운트 증가
                if (prev.equals(next)) count++;
                // 단위가 달라지면 압축된 형태로 저장
                else {
                    if (count > 1) sb.append(count);  // 반복 횟수 추가
                    sb.append(prev);  // 이전 단위 저장
                    prev = next;  // 다음 단위로 갱신
                    count = 1;  // 카운트 초기화
                }
            }
            
            // 남은 문자열 처리
            if (count > 1) sb.append(count);
            sb.append(prev);  // 마지막 단위 저장
            
            // 최소 길이 갱신
            result = Math.min(result, sb.length());
        }
        
        return result;  // 가장 짧은 압축 문자열의 길이 반환
    }
}

 Approaches

이 문제는 문자열을 다양한 단위로 분할하여 압축하는 방식으로 최적의 압축 길이를 찾는 문제입니다. 각 분할 단위에서 반복되는 문자열을 탐색하고, 그 결과를 조합하여 가장 짧은 길이의 문자열을 도출하는 과정이 핵심입니다.

1. 문제 분석

이 문제는 주어진 문자열을 다양한 길이의 단위로 나누어 가장 짧은 압축 문자열의 길이를 찾는 방식으로 해결할 수 있습니다. 이를 위해, 문자열의 길이의 절반까지 단위를 늘려가며 각 경우를 비교합니다. 각 단위별로 문자열을 자르고, 연속된 패턴이 반복될 때 압축하여 새로운 문자열을 생성한 후, 그 길이를 측정합니다. 최종적으로, 모든 단위에 대해 압축한 결과 중 가장 짧은 길이를 선택합니다.

2. 접근 방식

주어진 문자열을 1개 단위부터 최대 문자열 길이의 절반까지 잘라서 각 단위별로 압축 길이를 계산하고, 그중 가장 짧은 압축 길이를 찾습니다. 이를 위해 다음과 같은 단계를 거쳐 문제를 해결합니다:

  • 단위 길이 설정: 1자리부터 최대 전체 문자열 길이의 절반까지 모든 단위를 시도합니다. 단위 길이가 전체 문자열의 절반을 초과하면 더 이상 압축될 수 없기 때문에, 그 이하의 길이만 고려합니다.
  • 문자열 자르기 및 비교: 설정한 단위 길이만큼 문자열을 잘라 각 단위 문자열을 순차적으로 비교하여 동일한 문자열이 연속되는지를 확인합니다.
  • 압축 문자열 생성: 반복되는 단위가 있으면 반복 횟수를 누적하여 압축 형태의 문자열을 생성합니다. 동일한 단위가 반복되지 않으면 현재까지의 압축 문자열을 완성하고, 다음 단위로 이동하여 계속 비교합니다.
  • 최소 길이 갱신: 각 단위별로 생성된 압축 문자열의 길이를 계산하고, 이전 길이와 비교하여 가장 짧은 길이로 갱신합니다. 이를 모든 단위에 대해 반복한 후, 최종적으로 최소 길이를 반환하여 문제를 해결합니다.
3. 초기 변수 설정 및 기본 길이 계산

먼저, 문자열을 압축하기 전에 결과를 저장할 변수를 초기화합니다. 이 변수는 현재 문자열의 최소 길이를 추적하기 위해 사용되며, 최대값인 압축하지 않은 원본 문자열의 길이를 설정합니다. 이후 이를 활용하여 각 단위별 압축 문자열과 비교하면서 최소 값을 업데이트합니다.

Solution.java
// 초기값: 압축하지 않은 원본 문자열의 길이
int result = s.length();
4. 압축 단위 길이 설정 및 첫 번째 단위 문자열 초기화

문자열을 압축할 때 사용할 단위 길이는 최소 1부터 시작하여 문자열 전체 길이의 절반까지 설정할 수 있습니다. 단위 길이가 절반을 초과하게 되면 더 이상 유효한 반복 패턴을 만들 수 없기 때문입니다. 따라서 가능한 모든 단위 길이에 대해 문자열을 압축하여 가장 짧은 결과를 찾는 과정을 진행합니다.

먼저, 설정된 단위 길이로 문자열의 첫 번째 부분을 추출하여 비교의 기준점으로 설정합니다. 이 첫 번째 단위 문자열은 이후의 단위 문자열들과 비교하는 기준이 됩니다. 또한, 단위 문자열이 몇 번 반복되는지를 추적하기 위한 변수도 초기화합니다.

이렇게 단위 길이와 첫 번째 단위 문자열을 설정한 후, 다음 단위 문자열과의 비교를 시작하게 됩니다.

Solution.java
for (int i = 1; i <= s.length() / 2; i++) {
    String prev = s.substring(0, i);  // 첫 번째 단위 문자열 설정
    int count = 1;  // 반복 횟수 초기화
    ...
}
5. 인접 단위 문자열 비교 및 압축 수행

설정된 단위 길이로 나눈 문자열을 차례대로 비교하며 압축을 진행합니다. 이 과정에서는 현재 단위 문자열과 다음 단위 문자열이 동일한지 확인하여 반복되는 경우를 추적합니다.

만약 두 단위 문자열이 동일하다면, 반복 횟수를 증가시키고 다음 단위로 이동합니다. 반대로, 현재 단위와 다음 단위가 다를 경우, 지금까지의 반복 횟수와 현재 단위 문자열을 압축된 결과에 추가합니다. 반복이 2회 이상일 때만 숫자를 붙여서 압축된 형태로 저장하며, 1회인 경우에는 숫자를 생략하고 그대로 문자열만 저장합니다.

이렇게 단위별로 반복 비교를 통해 압축을 수행하면서, 현재 단위를 다음 단위로 갱신하고 반복 횟수도 초기화합니다. 이 과정을 문자열 끝까지 반복하여 모든 단위 문자열을 처리합니다.

Solution.java
for (int i = 1; i <= s.length() / 2; i++) {
    ...
    
    StringBuilder sb = new StringBuilder();
    for (int j = i; j < s.length(); j += i) {  // 현재 단위 길이만큼 이동하면서 반복 확인
        String next = i + j > s.length() ? s.substring(j) : s.substring(j, i + j);  // 다음 단위 문자열 설정
        
        if (prev.equals(next)) {  // 동일한 단위가 반복될 때
            count++;
        } else {  // 반복이 끝나면 압축된 형태로 저장
            if (count > 1) sb.append(count);  // 반복 횟수가 2 이상일 때만 숫자 추가
            sb.append(prev);  // 현재 단위 문자열 추가
            prev = next;  // 다음 단위로 갱신
            count = 1;  // 반복 횟수 초기화
        }
    }
}
6. 마지막 단위 문자열 처리

모든 단위 문자열을 순차적으로 비교하고 압축하는 과정이 끝나면, 마지막으로 비교한 단위 문자열이 처리되지 않고 남아있을 수 있습니다. 이는 반복이 끝나기 직전까지 동일한 단위가 계속 반복되어 카운트 값만 증가한 상태로, 비교할 대상이 없어 탐색이 종료되었기 때문입니다. 이 경우, 마지막 남은 단위 문자열과 그 반복 횟수가 최종 압축 문자열에 추가되지 않아 압축이 불완전하게 끝나게 됩니다.

따라서, 탐색이 종료된 후에도 반복 횟수와 남아 있는 단위 문자열을 최종적으로 압축 문자열에 추가하여 모든 단위가 올바르게 반영되도록 처리해야 합니다.

Solution.java
for (int i = 1; i <= s.length() / 2; i++) {
    ...
    for (int j = i; j < s.length(); j += i) {...}
    
    // 남은 문자열 처리
    if (count > 1) sb.append(count);  // 마지막 남은 단위 문자열 반복 횟수 추가
    sb.append(prev);  // 마지막 남은 단위 문자열 추가
}
7. 압축 문자열 최소 길이 갱신

각 단위 길이에 대해 압축을 완료한 후, 현재 압축된 문자열의 길이를 확인하고, 이전에 기록된 최소 길이와 비교하여 갱신합니다. 이를 통해 각 단위 길이별로 압축된 문자열 중 가장 짧은 길이를 찾을 수 있으며, 최종적으로 최소 압축 길이가 결정됩니다. 이 과정은 모든 가능한 단위 길이에 대해 반복되며, 최종적으로 가장 짧은 압축 문자열 길이를 반환하게 됩니다.

Solution.java
// 최소 길이 갱신
result = Math.min(result, sb.length());
8. 가장 짧은 압축 문자열의 길이 반환

모든 단위 길이에 대한 압축이 완료된 후, 가장 짧은 압축 길이를 도출하여 반환합니다. 이렇게 계산된 최소 길이가 최적의 압축 결과를 나타내며, 최종적으로 압축된 문자열의 최소 길이를 출력하게 됩니다.

Solution.java
// 가장 짧은 압축 문자열의 길이 반환
return result;

󰄉 Complexity

  • TC: O(n^2)
  • 💾 SC: O(n)

문자열을 최대 절반 길이까지 나누어 압축하기 때문에, 각 경우의 문자열 비교와 압축 과정이 전체 문자열 길이의 제곱에 비례합니다. 문자열 길이가 최대 1000이므로, 이 문제는 최악의 경우에도 충분히 해결할 수 있습니다.

  • Algorithm
  • String