[Programmers] 문자열 압축

문자열 압축

level 2

2020 KAKAO BLIND RECRUITMENT

 

python 3

# 문자열을 step 단위로 토크나이징 한 뒤, 각 토큰 별 반복횟수를 이차원 배열로 만드는 함수
def compress(s, step):
    countStack = []
    tokenList = [s[i: i + step] for i in range(0, len(s), step)]

    for token in tokenList:
    	# 첫번째 토큰은 스택에 바로 넣어줍니다.
        if len(countStack) == 0:
            countStack.append([token, 1])
        # 두번째 토큰 부터는 이전 토큰과 동일한지 검사합니다.
        else:
            lastIndex = len(countStack) - 1
            if countStack[lastIndex][0] == token:
                countStack[lastIndex][1] += 1
            else:
                countStack.append([token, 1])
                
    return countStack


# compress 함수를 통해 만들어진 이차원 배열을 문자열로 변환하는 함수
def encode(stack):
    return "".join(
        map(lambda tokenFair: '{0}{1}'.format('' if tokenFair[1] == 1 else tokenFair[1], tokenFair[0]), stack))


def solution(s):
    # 압축된 문자열을 구합니다
    encodedList = [encode(compress(s, step)) for step in range(1, len(s) + 1)]
    # 압축된 문자열의 길이를 구합니다
    lengthList = map(lambda encoded: len(encoded), encodedList)

    return min(lengthList)

우선 브루트 포스 방식으로.. 풀었습니다.

문제에서 문자열을 압축하기 위한 방식이 일정한 길이로 앞에서부터 자르는 것이기 때문에, 각 step 별로 압축한 길이를 비교해서 제일 짧은 것을 반환하면 됩니다.

문자열을 일정한 단위로 자른 문자열 배열을 만든 뒤, 해당 배열과 스택을 이용해서 토큰과 토큰 개수의 이차원 배열을 만들어줍니다.

이렇게 만들어진 이차원 배열을 돌면서 문자열로 만들어, 길이를 비교하여 제일 적은 것을 반환하면 됩니다.