[프로그래머스 2020 KAKAO BLIND RECRUITMENT] 문자열 압축

programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

레벨 2에 해당하는 문제

문자열 처리는 파이썬으로 하자!

 

문제가 다행히 모든 문자에 대해 반복을 찾는게 아니었다.

문자열 길이를 2로 설정한다면

시작 인덱스가 0, 2, 4 ... 이런 식으로 반복을 검사하는 것이었다.

알고리즘보다는 구현에 가까운 문제로

 

for 문자열 길이 in range(1부터 전체 문자열 절반까지)

  for 전체 문자열 순회하기

 

의 구조이다.

 

파이썬을 잘 몰라서 함수 활용을 많이 못했다 ㅠㅠ

새로 알게된 기능은

 

1. range (start, end, dis):

start부터 end-1까지 dis 간격으로 조회

한마디로 for문에서 연산부분 i+=dis에 해당하는 부분이다. 

 

2. 정수 길이 파악

c계열 언어에 비해 파이썬의 이런 점이 문자열 처리에 유리한 듯 싶다.

len('{}'.format(정수))

len(str(정수))

둘 다 가능하다.

 

def solution(s):
    answer = len(s)
    
    for dis in range(1, int(len(s)/2)+1):
        cmp = ''
        cnt = 1
        res = 0
        for i in range(0, len(s), dis):
            cur = s[i:i+dis]
            
            if cur == cmp:
                cnt+=1
            else :
                res += len(cur)
                if cnt>1:
                    res += len('{}'.format(cnt))
                cnt = 1
                cmp = cur
        if cnt>1:
            res += len('{}'.format(cnt))
        answer = min(answer, res)
                
    return answer

 

 

++ 다른 사람이 쓴 풀이 중 조금 더 파이썬스러운 코드를 보았다.

 

words에 길이로 자른 문자열 배열을 미리 넣어 놓고 

zip을 사용하여 비교한다.

for a,b in zip(list1, list2)는 길이가 동일한 두 개의 리스트에 대해 동일한 위치의 iterator a,b를 생성하는 것이다.

 

def compress(s, s_len):
    words = [s[i:i+s_len] for i in range(0, len(s), s_len)]
    
    res = []
    cur_word = words[0]
    cur_cnt = 1
    
    for a, b in zip(words, words[1:] + ['']):
        if a==b:
            cur_cnt += 1
        else:
            res.append([cur_cnt, cur_word])
            cur_word = b
            cur_cnt = 1
    return sum(len(word) + (len(str(cnt)) if cnt>1 else 0) for cnt, word in res)

def solution(s):
    if len(s)==1:
        return 1
    return min(compress(s, i) for i in range(1, int(len(s)/2)+1))