문제 링크

문제 간단 해석

문자열을 일정 길이로 쪼개고, 반복되는 문자열을 찾아 압축했을 때 가장 짧게 압축할 수 있는 길이를 구한다.
이번에도, 두 풀이의 방향성이 살짝 다르다.

Java

문제가 요구하는 것처럼, 압축한 String 형태로 길이를 구한다.

풀이 코드

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

class Solution {
    public int solution(String s) {
        List<String> sl = new ArrayList<>();
        int answer = s.length();
        String before;
        String now;
        int count;
        
        for (int i = 1; i <= s.length() / 2; i++) {
            sl.clear();
            before = "";
            now = "";
            count = 1;
            
            for (int j = 0; j < s.length(); j+=i) {
                try {
                    now = s.substring(j, j + i);
                } catch (StringIndexOutOfBoundsException e) {
                    now = s.substring(j);
                }
                
                if (now.equals(before)) {
                    count++;
                } else {
                    if (count > 1)
                        sl.add(Integer.toString(count));
                    
                    sl.add(before);
                    before = now;
                    count = 1;
                }
            }
            if (count > 1)
                sl.add(Integer.toString(count));
            sl.add(now);
            answer = Math.min(answer, String.join("", sl).length());
        }
        
        return answer;
    }
}

해석

List<String> sl = new ArrayList<>();
int answer = s.length();
String before;
String now;
int count;

String을 담을 List, 결과 최대값(압축되지 않은 원본의 길이), 이전 문자열, 현재 문자열, 문자열이 반복된 갯수를 선언한다.

for (int i = 1; i <= s.length() / 2; i++) {
    sl.clear();
    before = "";
    now = "";
    count = 1;
	
    ...
    
}

문자열의 단축은 s / 2를 넘어갈 경우 의미가 없으므로 s / 2까지만 반복한다.
또한 반복 전 String List를 포함한 값들을 초기화한다.

for (int j = 0; j < s.length(); j+=i) {
    try {
        now = s.substring(j, j + i);
    } catch (StringIndexOutOfBoundsException e) {
        now = s.substring(j);
    }

    if (now.equals(before)) {
        count++;
    } else {
        if (count > 1)
            sl.add(Integer.toString(count));

        sl.add(before);
        before = now;
        count = 1;
    }
}

문자열을 자를 시작 위치를 j로 선언하고 i로 정해진 글자 수만큼 자른다. 만약 해당 글자수만큼 자를 수 없다면(j + i가 s의 길이를 넘어간다면) j 위치부터 끝까지 자른다.
이전에 자른 글자와 현재 자른 글자가 일치한다면 count를 늘린다. 아니라면 List에 count를 추가하되, count는 1을 초과했을 때만(문자열이 한번이라도 반복되었을 때만) 추가한다. 그 후 이전 문자열과 count를 변경한다.

if (count > 1)
    sl.add(Integer.toString(count));
sl.add(now);
answer = Math.min(answer, String.join("", sl).length());

반복이 끝날 시 count와 현재 문자열을 추가한다. 또한 answer를 최소값으로 유지한다.
해당하는 answer를 반환하면 끝.

Python

글자 수만 구하면 되므로, 조금 더 쉬운 접근을 하였다. 다만 실제 코딩테스트에서는 예외를 눈으로 직접 확인해보며 문제를 풀어야 할 수도 있으니, 별로 추천하진 않는다.

풀이 코드

def digit(n):
    num = 0
    if 1 < n:
        num = len(str(n))
        
    return num


def solution(s):
    answer = len(s)
    
    for unit in range(1, (len(s) // 2) + 1):
        st = s[:unit]
        cnt = 1
        total = 0
        
        for step in range(unit, len(s), unit):
            nxt = s[step: step + unit]
            
            if st == nxt:
                cnt += 1
            else:
                total += len(st) + digit(cnt)
                st = nxt
                cnt = 1

        else:
            total += len(st) + digit(cnt)
        
        answer = min(answer, total)
        
    return answer

해석

def digit(n):
    num = 0
    if 1 < n:
        num = len(str(n))
        
    return num

숫자를 글자로 변환 후 그 길이만큼만 return하는 함수를 작성했다.

answer = len(s)

초기값은 s의 전체 길이로 잡았다.

for unit in range(1, (len(s) // 2) + 1):
	st = s[:unit]
	cnt = 1
	total = 0
	
	for step in range(unit, len(s), unit):
	    nxt = s[step: step + unit]
	    
	    if st == nxt:
	        cnt += 1
	    else:
	        total += len(st) + digit(cnt)
	        st = nxt
	        cnt = 1
	
	else:
	    total += len(st) + digit(cnt)
	
	answer = min(answer, total)
    
return answer

이 역시 반복은 s / 2까지만 한다.
문자열을 잘라 가며 이전값과 비교하고, 같으면 1을 증가시킨다. 아니라면 잘라낸 문자열과 cnt만큼의 길이를 더한다.
answer를 매 반복마다 최소값으로 유지해주고, 마지막에 return하면 끝.