문자열 압축

이 문제는 2020 카카오 신입 공채에 나온 문제이다. 입력으로 주어지는 s의 길이는 1000이하이기 때문에 완전탐색이 가능하다. 그러나 절반이 넘어가는 부분문자열의 개수에 대해서는 따로 체크할 필요는 없기 때문에 1 ~ len(s)//2까지 단계를 나눠서 체크를 하면 될 것 같다.

입출력의 예#4를 보면 2, 3, 4, 6인 경우를 비교해서 최소값을 찾는 것을 볼 수 있다.
그래서 나도 위와 같이 단계별로 나눠서 코딩을 했다.

여기서 중요한 포인트는 최신화라 생각을 했다.
항상 기준 부분 문자열이 변경되고, 동일한 부분 문자열의 개수를 세줘야 하는 것이 가장 키포인트였다.
기준 부분 문자열이 변경되는 경우와 부분 문자열의 개수가 변경되는 경우는 아래와 같다.

기준 부분 문자열과 비교하는 부분 문자열이 다른 경우

우리는 기준 부분 문자열과 비교하는 부분 문자열이 다른 경우에 대해서 체크를 해줘야한다.
부분 문자열을 만드는데는 파이썬의 list slice가 매우 편했다.
내가 개발한 소스코드는 아래와 같다.

def solution(s):
    answer = 0
    sLen = len(s)  # 문자열 전체 길이 저장
    minValue = sLen  # 초기 최소값은 문자열 전체 길이
    
    criteria = 0  # 기준값
    if sLen % 2 == 1:  # 홀수인 경우 가운데 위치는 2를 나눈 몫에서 1을 더해야함
        criteria = sLen // 2 + 1
    else:
        criteria = sLen // 2
    
    for i in range(1, criteria + 1):  # 1 ~ 절반 길이까지로 나눠서 비교
        sameStrCount = 1  # 초기 같은 문자열의 개수
        criteriaStr = s[0:i]  # 첫번째 기준 문자열
        compressed = ''  # 반복된 문자열 적용해서 저장하는 변수
        for j in range(i, sLen, i):  # i부터 전체 길이까지 i만큼 증가하면서 반복문 진행
            if criteriaStr == s[j:j + i]:  # 기준 문자열과 부분 문자열 비교해서 같은 경우
                sameStrCount += 1  # 같은 문자열 개수를 저장하는 변수 1 더해줌
            else:  # 반복 문자열과 부분 문자열 비교해서 다른 경우
                if sameStrCount > 1:  # 같은 문자열 개수가 1보다 큰 경우
                    compressed += str(sameStrCount) + criteriaStr  # 숫자 포함해서 문자 연결
                else:  # 같은 문자열 개수가 1보다 작거나 같은 경우
                    compressed += criteriaStr  # 문자만 연결
                criteriaStr = s[j:j + i]  # 기준 문자열 최신화
                sameStrCount = 1  # 개수 최신화
        
        # 마지막 로직 체크
        if sameStrCount > 1:  # 같은 문자열 개수가 1보다 큰 경우
            compressed += str(sameStrCount) + criteriaStr  # 숫자 포함해서 문자 연결
        else:  # 같은 문자열 개수가 1보다 작거나 같은 경우
            compressed += criteriaStr  # 문자만 연결
        minValue = min(len(compressed), minValue)  # 최솟값 저장
    
    answer = minValue  # 최솟값 answer 변수에 저장
    return answer

첫번째 for문은 비교를 할 부분 문자열의 길이를 나타낸다. 문자열의 절반길이 만큼 비교를 한다.
그런 다음 사용되는 변수들을 최신화해줬다.
sameStrCount가 1인 이유는 첫번째 기준 부분 문자열의 개수를 나타내기 때문이다.
criteriaStr은 부분 문자열의 길이만큼 slice를 해서 저장했다.
compressed는 압축된 문자열을 초기화하고 있다.

두번째 for문은 i부터 문자열 전체 길이까지다. 그런 다음 증가는 i만큼한다.
i만큼 증가시킨 이유는 부분 문자열의 길이만큼 보폭을 유지하기 위함이다.
여기서 이제 실질적인 기준 부분 문자열과 모든 부분 문자열들이 비교가 된다.
같은 경우는 단순 sameStrCount를 증가시켜주고,
sameStrCount가 1이하인 경우에는 따로 숫자까지 compressed에 저장할 필요가 없기 때문에
아닌 경우에는 또 2개의 조건으로 나눠서 저장한다.

두번째 for문을 빠져나온 뒤, 남아있는 기준 부분 문자열에 대해서 추가 작업을 한다.
그런다음 문자열 길이의 최솟값을 저장해서 노출시켜주면 된다.