99클럽 코테 스터디 3일차 TIL : 문자열 압축, StringBuilder

 

오늘의 학습 키워드

• 문자열 처리
• 압축을 통한 변환
• Java의 문자열 메서드 사용

오늘은 문자열을 특정 단위로 잘라서 반복되는 문자열을 압축하는 문제를 해결했습니다. 이를 위해 문자열을 다양한 단위로 잘라보고, 반복되는 문자열을 카운트하여 압축된 문자열의 길이를 구하는 방법을 배웠습니다. Java의 substring 메서드와 StringBuilder를 활용해 문자열을 처리했습니다.

오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

문자열을 특정 단위로 잘라서 반복되는 부분을 압축하여 가장 짧은 문자열을 찾는 문제였습니다. 처음에는 문자열을 단위로 자르는 방법과 반복되는 부분을 효율적으로 찾아내는 로직을 구현하는 데 어려움을 겪었습니다.

 

class Solution {
    public int solution(String s) {
        int sLength = s.length();
        // 압축된 문자열 중 가장 짧은 것의 길이 : 반환값
        int minLength = sLength;

        // 1개 단위부터 s_len/2개 단위까지 자르기 : 절반이 넘으면 압축 의미가 없음
        for (int unit = 1; unit <= sLength / 2; unit++) {
            int compressedSLength = getCompressedSLength(s, unit, sLength);
            minLength = Math.min(minLength, compressedSLength);
        }

        return minLength;
    }

    /**
    * unit 단위로 잘라서 압축 후 압축된 문자열의 길이 반환
    */ 
    private int getCompressedSLength(String s, int unit, int sLength) {
        StringBuilder compressedS = new StringBuilder();
        int count = 1; // 현재 단위의 문자열이 반복되는 횟수

        for (int i = 0; i < sLength; i += unit) {
            int currentEnd = Math.min(i + unit, sLength); // 현재 단위 문자열의 끝
            String current = s.substring(i, currentEnd); // 현재 단위 문자열
            
            if (i + unit < sLength) {
                int nextEnd = Math.min(i + 2 * unit, sLength);
                String next = s.substring(i + unit, nextEnd);

                if (current.equals(next)) {
                    count++;
                } else {
                    appendCompressedS(compressedS, count, current);
                    count = 1;
                }
            } else { // 마지막 남은 문자열 처리
                appendCompressedS(compressedS, count, current);
            }
        }

        return compressedS.length();
    }

    /**
    * 압축 표현
    */
    private void appendCompressedS(StringBuilder compressedS, int count, String current) {
        if (count > 1) {
            compressedS.append(count).append(current);
        } else {
            compressedS.append(current);
        }
    }
}

/*
시간 복잡도 계산 : O(nlogn)

외부 반복문 - O(n/2)
내부 반복문 - O(n/unit)
*/

 

 

어떻게 해결했는지
보다 효율적인 접근 방법으로 문자열을 1부터 sLength/2 단위까지 잘라가며 반복되는 부분을 찾아내고, 이를 압축하여 가장 짧은 문자열의 길이를 구하는 방법을 사용했습니다. 이를 통해 문자열의 단위별로 압축된 길이를 구하고, 최종적으로 가장 짧은 압축된 문자열을 찾을 수 있었습니다.

 

무엇을 새롭게 알았는지
문자열을 자르고 압축하는 과정에서 `StringBuilder`를 사용하면 효율적으로 문자열을 처리할 수 있음을 배웠습니다. 또한, 반복되는 문자열을 찾는 로직을 작성하는 데 있어 문자열 비교와 문자열 길이 계산을 적절히 활용하는 방법을 알게 되었습니다.

 

내일 학습할 것은 무엇인지
시간복잡도 계산