Search

문자열 압축

문제 : 문자열 압축

문제 요약 : 주어진 문자열을 가장 짧게 줄이자!

ex) ababcdcdababcdcd
문자 1개 단위로 쪼개는 경우
압축 X → ababcdcdababcdcd
문자 2개 단위로 쪼개는 경우
ab ab cd cd ab ab cd cd2ab 2cd 2ab 2cd → 문자열 길이 12
문자 8개 단위로 쪼개는 경우
ababcdcd ababcdcd2ababcdcd→ 문자열 길이 9 : 최솟값!

풀이

해결에 필요한 핵심 아이디어: slice 함수로 각 단위 별로 문자열 압축 반복

해결 시나리오

slice 함수를 사용해 단위를 1부터 문자열의 전체 길이까지 잘라보며 모든 경우를 테스트
각각 단위 별로 테스트하며 압축한 문자열을 results 리스트에 저장
results에 담긴 압축 문자열 중 가장 짧은 길이를 결과로 반환
답안
def solution(s): # 각각 단위(1, 2, 3... len(s))로 자른 문자열 길이를 저장할 리스트 results = [] # 1부터 s의 길이까지 반복하면서 for i in range(1, len(s) + 1): # 문자열 자르기 sliced = [] # 자른 문자열 파트를 담을 리스트 for j in range(0, len(s), i): sliced.append(s[j:j + i]) # i == 1 -> s[0:1], s[1:2], s[2:3]... sliced = ['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c'] # i == 2 -> s[0:2], s[2:4], s[4:6]... sliced = ['aa', 'bb', 'ac', 'cc'] # 자른 문자열들을 서로 비교하며 문자열 압축 parts = [] # 중복된 문자열을 제거한 파트를 담을 리스트 nums = [] # 반복되는 파트를 카운트한 숫자를 담을 리스트 cnt = 1 # 자른 문자열 파트를 앞뒤로 비교 # sliced = ['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c'] for j in range(1, len(sliced)): if sliced[j] == sliced[j - 1]: cnt += 1 else: parts.append(sliced[j - 1]) if cnt == 1: cnt = '' nums.append(str(cnt)) cnt = 1 # 앞선 반복문에서 누락된 마지막 문자열 파트에 대한 처리 parts.append(sliced[-1]) if cnt == 1: cnt = '' nums.append(str(cnt)) # sliced = ['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c'] # parts = ['a', 'b', 'a', 'c'] # nums = [2, 2, '', 2] # 문자열 압축 결과를 result 변수에 저장 result = '' for j in range(len(nums)): result += (nums[j] + parts[j]) # 2a + 2b + a + 2c -> 2a2ba2c # results 리스트에 각각 단위로 잘라서 압축한 문자열의 길이를 저장 results.append(len(result)) return min(results)
Python

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.