프로그래머스 - 2020 KAKAO BLIND RECRUITMENT 문자열 압축
내 풀이
'''
Problem Solving Programmers 60057
Author: Injun Son
Date: February 23, 2021
'''
import sys
import collections
import heapq
import functools
import itertools
import re
import math
import bisect
def compress_string(answer, length, s):
words = cut_string(length, s)
words = words + ["Z"]
prev = "A"
count = 0
tmp_string = ""
for word in words:
if word == prev:
count += 1
else:
if count > 1:
tmp_string += str(count) + prev
else:
tmp_string += prev
count = 1
prev = word
answer.append(tmp_string[1:])
def cut_string(length, s):
words = []
prev = 0
while prev + length < len(s):
words.append(s[prev: prev + length])
prev += length
if prev < len(s):
words.append(s[prev:])
return words
def solution(s):
answer = []
for i in range(1, len(s)+1):
compress_string(answer, i, s)
# print(answer)
return min(len(x) for x in answer)
print(solution("aabbaccc"), 7)
print(solution("ababcdcdababcdcd"), 9)
print(solution("abcabcdede"), 8)
print(solution("abcabcabcabcdededededede"), 14)
print(solution("xababcdcdababcdcd"), 17)
print()
print(solution("aababa"), 5)
print(solution("aaaaaaaaaab"), 4)문자열을 하나씩 자를지, 두개씩 자를지 완전탐색을 한다. cut_string함수는 몇 개씩 자를지 매개변수로 받아서 list로 돌려주는 함수이다. index error가 발생하지 않게 마지막 전에 미리 끝내고, 남아있으면 남은거를 더해주는 방식이다.
compress_string 함수는 압축해주는 함수인데 예를 들어 ['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c'] 이렇게 있으면 '2a2ba3c' 로 압축해준다. 예전 네이버 부스트캠프에도 이런 중복되는 것을 카운팅하는 문제가 나왔는데, 리스트에 절대 들어 올 수 없는 문자를 뒤에 붙여주는 방식이 괜찮은 것 같다. (여기서는 소문자만 들어오므로 앞 뒤에 대문자를 붙여줬다). prev에는 절대 올 수 없는 문자인 "A"를 붙여줬는데, 이는 실제 string의 첫 문자를 만나면 바로 리뉴얼 될 것이다. 그리고 이 부분은 마지막에 return 할 때 제거하면된다. 마지막에 Z를 붙인 것은, 그렇지 않았을 때 "ccc"부분에서 count만 올라가고 string에 붙여지지 않고 끝날 수 있기 때문에 강제로 항상 끝을 내주기 위해서이다.
처음에 틀렸는데, 틀린 이유가 aaaaaaaaaab=> 10ab => 4 같은 경우를 고려하지 못했는데, int형을 str으로 바꿀 때는 항상 조심해야한다.
cut_string 함수를 파이써닉하게 대체할 수 있다.
[s[i:i+length] for i in range(0, len(s), length)]끝 인덱스를 초과하면 에러가 난다고 생각했는데 슬라이싱은 끝 인덱스를 초과해도 괜찮다.
a = [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] print(a[0:20]) # 인덱스 0부터 9까지 잘라서 새 리스트를 만듦출력 결과: [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
간단해진 코드
def compress_string(answer, length, s):
words = [s[i:i+length] for i in range(0, len(s), length)]
words = words + ["Z"]
prev = "A"
count = 0
tmp_string = ""
for word in words:
if word == prev:
count += 1
else:
if count > 1:
tmp_string += str(count) + prev
else:
tmp_string += prev
count = 1
prev = word
answer.append(tmp_string[1:])
def solution(s):
answer = []
for i in range(1, len(s)+1):
compress_string(answer, i, s)
return min(len(x) for x in answer)유사한 문제
