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

 

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

문제 풀이

이 문제의 핵심은 문자열을 정해진 길이만큼 잘라 내는 것이다. 자바에서는 이것을 substring() 메서드를 사용하여 쉽게 구현 가능하다. 압축했을 때 가장 짧은 문자열의 길이를 구해야 하는데, 이는 모든 길이에 대하여 압축을 시도한 후 그 중 가장 짧은 길이를 선택하면 된다. 이를 바탕으로 다음과 같이 작성할 수 있다.

 

문제 풀이 흐름

1. 1부터 입력 문자열 s의 길이만큼 자를 문자열의 길이를 설정하며 반복
2. 설정된 길이만큼 문자열을 잘라 낸 token의 배열 생성
3. 문자열을 비교하며 token의 배열을 하나의 문자열로 압축
4. 1~3 과정으로 압축된 문자열 중 가장 짧은 길이 반환

코드 작성

1. 1부터 입력 문자열 s의 길이만큼 자를 문자열의 길이를 설정하며 반복

먼저 자를 문자열의 길이를 반복문을 이용해 설정하고 가장 짧은 압축 문자열의 길이를 담을 min 변수를 선언하고 반환한다. 자를 문자열의 길이는 최소 1부터 시작하여 문자열 전체 길이를 포함하도록 반복한다. 

 

class Solution {
    public int solution(String s) {
        int min = 0;
        for(int length = 1; length <= s.length; length++) {
            //문자열 압축 후 가장 짧은 길이 선택
        }
        return min;
        
    }
}

 

 

이제 문자열을 압축하고 압축된 문자열의 길이를 반환하는 compress() 메서드를 선언한다.

 

private int compress(String source, int length) {
        // 압축한 문자열 길이를 반환
    }

 

2. 설정한 길이만큼 문자열을 잘라 낸 token의 배열 생성

그런데 압축하려면 우선 length 길이씩 문자열을 잘라야 한다. 다음과 같이 문자열을 length 길이씩 잘라 리스트에 담아주는 split() 메서드를 선언한다. 

 

private List<Stirng> split(String source, int length) {
        List<String> tokens = new ArrayList<>();
        //source를 length만큼씩 잘라 tokens 리스트에 추가
        return tokens
    }

 

문자열을 자르는 시작 인덱스는 0부터 시작하여 length만큼 증가한다. 따라서 다음 반복문으로 모든 startIndex를 순회할 수 있다.

 

for(int startIndex = 0; startIndex < source.length; startIndex+=length;) {
            // 문자열을 startIndex부터 잘라 tokens 리스트에 추가
        }

 

이때 endIndex는 startIndex + length이지만 문자열 범위 밖을 넘어가지 않게 하기 위해 다음과 같이 작성한다.

 

int endIndex = startIndex + length;
if(endIndex > source.length())  endIndex = source.length();

 

이제 실제로 문자열을 잘라 tokens 리스트에 추가한다.

 

tokens.add(source.substring(strartIndex, endIndex));

 

이렇게 완성된 split() 메서드를 이용하여 compress() 메서드에서는 tokens 리스트를 만들고, 문자열을 구성할 StringBuilder 객체를 생성한다.

 

 private int compress(String source, int length) {
    StringBuilder builder = new StringBuilder();

    for(String token: split(source, length)) {
        // 압축 문자열 구성
    }
    return builder.length();

}

 

3. 문자열을 비교하며 token의 배열을 하나의 문자열로 압축

연속으로 중복된 문자열을 검사해야 하므로 직전에 등장한 문자열을 담는 last 변수와 그 등장 횟수를 담는 cnt 변수를 선언한다. 

 

String last = "";
int cnt = 0;
for(String token: split(source, length)) {
    // 압축 문자열 구성
}

 

현재 검사하는 문자열 token이 직전에 등장한 문자열과 같다면 등장 횟수만 증가해주면 된다.

 

for(String token: split(source, length)) {
    // 압축 문자열 구성
    if(token.equals(last))  cnt++;
    else {
        //새로운 동작
    }
}

 

새로운 토큰이 등장했다면 직전까지 등장한 문자열을 이용하여 압축 문자열을 구성해준다. 이때 등장 횟수 cnt는 2 이상일 때만 압축 문자열에 포함되고, 압축 문자열을 구성한 후에는 현재 검사한 token부터 다시 셀 수 있도록 last와 count를 업데이트 해야한다. 

 

else {
    //새로운 동작
    if(count > 1)   builder.append(count);
    builder.append(last);
    last = token;
    cnt = 1;
}

 

이렇게 for문을 나오면 아직 마지막 토큰은 last에 담긴채로 압축 문자열에 포함되지 않은 상태이다. 따라서 압축 문자열을 구성하는 로직을 for문 이후에 1회 더 추가해야 한다. 

 

for(String token: split(source, length)) {
    // 압축 문자열 구성
    if(token.equals(last))  cnt++;
    else {
        //새로운 동작
        if(count > 1)   builder.append(count);
        builder.append(last);
        last = token;
        cnt = 1;
    }
}
if(count > 1)   builder.append(count);
builder.append(last);

 

4. 1~3 과정으로 압축된 문자열 중 가장 짧은 길이 반환

solutiuion() 메서드에서는 이를 사용하여 각 토큰 길이별로 압축 문자열의 길이를 구하고, 가장 짧은 길이를 반환하면 된다. 

 

전체코드

 

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int solution(String s) {
        int min = Integer.MAX_VALUE;
        for(int length = 1; length <= s.length(); length++) {
            //문자열 압축 후 가장 짧은 길이 선택
            int compressed = compress(s, length);
            if(compressed < min)    min = compressed;
        }
        return min;
        
    }
    private List<String> split(String source, int length) {
        List<String> tokens = new ArrayList<>();
        //source를 length만큼씩 잘라 tokens 리스트에 추가
        for(int startIndex = 0; startIndex < source.length(); startIndex+=length) {
            // 문자열을 startIndex부터 잘라 tokens 리스트에 추가
            int endIndex = startIndex + length;
            if(endIndex > source.length())  endIndex = source.length();
            tokens.add(source.substring(startIndex, endIndex));
        }
        return tokens;
    }
    private int compress(String source, int length) {
        StringBuilder builder = new StringBuilder();
        String last = "";
        int cnt = 0;
        for(String token: split(source, length)) {
            // 압축 문자열 구성
            if(token.equals(last))  cnt++;
            else {
                //새로운 동작
                if(cnt > 1)   builder.append(cnt);
                builder.append(last);
                last = token;
                cnt = 1;
            }
        }
        if(cnt > 1)   builder.append(cnt);
        builder.append(last);
        return builder.length(); 
    }
}