[프로그래머스] 문자열 압축(JAVA)

| [프로그래머스] 문자열 압축

🗒️알고리즘 분류

#구현 #implementation

📌기억해야 할 포인트

특별한 알고리즘이 있는 줄 알았지만 문제에서 요구하는 사항만 정확하게 수행하면 되는 구현 문제이다.

• 반복문을 돌려주는 것만 유의해주면 된다.
  1. for (int chunkSize = 1; chunkSize <= length/2; ++chunkSize) : 최대로 압축을 해도 전체 문자열 길이의 반까지만 할 수 있으므로 반복문의 횟수를 문자열 길이의 반으로 제한한다.
  2. for (int i = 0; i <= length; i += chunkSize) : 이중 반복문으로 1번째 반복문에서 정한 길이를 지속적으로 잘라줘야 하기 때문에 다음 문자열의 시작점을 i += chunkSize 으로 설정한다.
  3. String cur = s.substring(i, Math.min(length, i+chunkSize)); : 비교하는 문자열(cur) 설정이다. 내가 생각하기에 이 문제의 가장 중요한 부분이다. 반복문을 계속 돌리다 보면 마지막 비교에서 압축 사이즈(chunkSize)가 문자열을 넘어가는 일이 발생한다. 그래서 문자열의 최대 길이보다 마지막에 자른 문자열의 크기(i+chunkSize)가 크다면 그것보다 작은 문자열의 길이(length)로 설정해준다. (Math.min(length, i+chunkSize))
  4. if (count > 1) {} else {}: 마지막까지 남은 prev/count 처리

📝풀이 코드(JAVA)

import java.util.*;

class Solution {
    public int solution(String s) {
        int length = s.length();
        int answer = length;
        
        for (int chunkSize = 1; chunkSize <= length/2; ++chunkSize) {
            int count = 0;
            String prev = s.substring(0, chunkSize);
            StringBuilder sb = new StringBuilder();
            
            for (int i = 0; i <= length; i += chunkSize) {
                String cur = s.substring(i, Math.min(length, i+chunkSize));
                
                if (prev.equals(cur)) {
                    ++count;
                } else {
                    if (count > 1) {
                        sb.append(count).append(prev);
                    } else {
                        sb.append(prev);
                    }
                    count = 1;
                    prev = cur;
                }
            }
            if (count > 1) {
                sb.append(count).append(prev);
            } else {
                sb.append(prev);
            }
            
            answer = Math.min(sb.length(), answer);
        }
        
        return answer;
    }
}

이것을 리팩토링하여 Lambda, Stream 으로 좀 더 간단하게 표현할 수도 있다.

📝 Lambda, Stream 풀이 코드(JAVA)

import java.util.stream.IntStream;

class Solution {

    public int solution(String s) {
        int length = s.length();
        // 1부터 length/2 까지의 모든 chunk 크기에 대해 compress 길이를 계산 → 최솟값
        return IntStream.rangeClosed(1, length / 2)
                        .map(chunkSize -> compress(s, chunkSize))
                        .min()
                        .orElse(length);    // 아무것도 못 찾으면 원본 길이
    }

    /**
     * 주어진 chunkSize 로 s 를 잘라서 연속된 같은 조각을 숫자+조각 문자열 형태로 압축했을 때의 길이 반환
     */
    private int compress(String s, int chunkSize) {
        StringBuilder sb = new StringBuilder();
        String prev = "";    // 직전 조각
        int count = 0;       // 같은 조각이 몇 번 연속됐는지

        for (int i = 0; i < s.length(); i += chunkSize) {
            String cur = s.substring(i, Math.min(s.length(), i + chunkSize));
            if (cur.equals(prev)) {
                count++;
            } else {
                // 새 조각이 나왔으니 이전까지 모아둔 count·prev 를 sb 에 붙이고
                if (count > 1) sb.append(count).append(prev);
                else sb.append(prev);
                prev = cur;
                count = 1;
            }
        }
        // 마지막까지 남은 prev/count 처리
        if (count > 1) sb.append(count).append(prev);
        else sb.append(prev);

        return sb.length();
    }
}

🆚2개의 풀이 비교

• for 문을 이용한 풀이: 메모리: 89.8 MB, 시간: 3.91 ms
• lamda, stream 을 이용한 풀이: 메모리: 75.4 MB, 시간: 6.28 ms

확실히 Lambda, Stream 을 이용한 풀이가 속도면에서 느리다는 것을 볼 수 있다.

⏰총 풀이시간

• 48분