2020 KAKAO BLIND RECRUITMENT Q1. 문자열 압축

조성권·2021년 8월 9일

Q1. 문자열 압축

1. 문제유형

Programmers 링크 공유
https://programmers.co.kr/learn/courses/30/lessons/60057

1-1. 입출력 예시

소스 코드

INF = int(1e9)

def solution(s):
    answer = INF
    
    if len(s) == 1: # 길이가 1일 때, return 1
        return 1
    
    for cutPoint in range(1,len(s)//2+1):
        ans = ""
        count = 1
        tmpStr = s[:cutPoint]
        
        for idx in range(cutPoint,len(s),cutPoint):
            if tmpStr == s[idx:idx+cutPoint]:
                count += 1
            else:
                if count == 1:
                    count = ""
                ans += str(count) + tmpStr
                tmpStr = s[idx:idx+cutPoint]
                count = 1
        
        if count == 1:
            count = ""
        
        ans += str(count) + tmpStr
        answer = min(answer,len(ans))
    
    return answer

3. 문제풀이

본 문제는 문자열을 다루는 알고리즘이며 문자열을 본인이 원하는 상태로 잘라낼 수 있는지가 키워드라 할 수 있다.

파이썬 문자열 자르는 방법
arr[A: B] > 범위: A ~ B-1 (인덱스 기준)
arr[A:] > 범위: A ~ 끝까지 (인덱스 기준
arr[:B] > 범위: 처음 ~ B-1 인덱스 기준)

위의 방식을 이해하고 있다면 조금은 쉽게 접근할 수 있다.

3-1. cutPoint 설정

먼저, 몇개의 잘린 문자열을 가지고 비교할 것인지 cutPoint를 세팅하는 작업을 할 것이다.

for cutPoint in range(1,len(s)//2+1):
	count = 1
	ans = ""
	tmpStr = s[:cutPoint]

tmpStr: 최초 문자열(=s)에서 cutPoint만큼만 잘라낸 문자열
count: 동일한 문자열 갯수 (초기값: 1)
ans: 현재 압축된 문자열이 저장될 변수

for문은 최초 문자열(=s) 길이의 절반을 초과하지 않도록 세팅
WHY? 절반을 넘어간다면 이미 압축이 의미없는 상황이기 때문

3-2. 비교 구문

이제 3-1에서 잘라낸 문자열(=tmpStr)과 비교하기 위한 for문을 구현할 것이다.

for idx in range(cutPoint, len(s), cutPoint):
	if tmpStr == s[idx:idx+cutPoint]:
		count += 1
	else:
		if count == 1:
			count = ""
		ans += str(count) + tmpStr
		tmpStr = s[idx:idx+cutPoint]
		count = 1

for문은 cutPoint값만큼 증가하도록 함으로써 같은 길이의 문자열이 비교될 수 있도록 한다.

만약, 기준 문자열(=tmpStr)과 다음 문자열(=s[idx:idx+cutPoint])가 동일할 경우, count += 1
그렇지 않을 경우,
1. 동일한 값이 1개 뿐이라면 생략한다고 문제에서 언급했기 때문에 "" 처리
2. ans에 현재까지의 동일한 갯수(=count) + 문자열(=tmpStr) 저장
3. tmpStr을 새로운 문자열로 재정의하고 count=1로 초기화

3-3. 최소 길이 구하기

3-2가 완료되어 for문을 탈출한 후, 해당 값이 최소길이인지 비교하는 절차가 필요하다.

if count == 1:
	count = ""
ans += str(count) + tmpStr
answer = min(answer, len(ans)

3-2의 for문을 탈출한 후, 한번 더 동일한 구문이 필요한 이유?

가장 마지막 문자열에 대해 처리하지 못했기 때문

위의 절차를 밟은 뒤, answer에 대해 기존의 answer과 현재 찾아낸 압축된 문자열(=ans)의 길이를 대사하여 더 작은 값을 answer에 다시 대입한다.

본 과정을 반복하면 결과적으로 answer에는 가장 작은 압축된 문자열 길이가 저장되는 것이다.

4. 마무리

오늘은 문자열을 다루는 알고리즘 문제를 풀어봤다. 파이썬은 그래도 문자열을 다루기 편하게 이루어져 있어서 그나마 편했지만 알고리즘을 생각해내는데 시간이 많이 걸리고 헤맸던 것 같다.
문제를 풀수록 더 잘 풀린다는 생각보다는 항상 난해하다는 생각이 많이 든다...ㅠ 아직 갈길이 멀다는 거겠지...
더 분주히 나아가야겠다!