[카카오 코딩테스트 / 프로그래머스] 문자열 압축 - 파이썬(Python3)

 

 

 

[카카오 코딩테스트 프로그래머스 문자열 압축

-> https://programmers.co.kr/learn/courses/30/lessons/60057

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

이번 문제는 2020 카카오 코딩테스트에 나온 문자열 압축 문제입니다!

상당히 쉬운 편이니 한번 풀어볼게요.

 

---

풀이 아이디어

 

이 문제는 문자열을 1개 단위로 잘라서 압축한것부터 len(문자열)//2 단위로 잘라서 압축한것까지 비교해주면 됩니다.

len(문자열)//2 를 넘어버리면 어차피 길이가 다른 두 문자열로 나눠지기 때문에 압축이 불가능하기 때문입니다.

 

굉장히 쉬우니 바로 구현해보도록 할게요 !

 

---

구현

 

먼저 문자열과 N을 전달하면 문자열을 N개 단위로 잘라 압축하고

압축된 문자열의 길이를 반환해주는 함수를 작성합니다.

 

그리고 1부터 len(문자열)//2 까지 이 함수에 전달해서 가장 작은 리턴값을 최종 리턴하면 문제가 요구하는 답이 됩니다.

 

그럼 이 문제의 포인트는 압축된 문자열의 길이를 반환해주는 함수를 구현하는 것입니다.

 

먼저 문자열을 N개씩 잘라서 저장합니다.

만약 문자열이 "ababcdcdabab" 이고

 

N=3 이면

list = ["aba", "bcd", "cda", "bac"],

 

N=2 이면

list = ["ab", "ab", "cd", "cd", "ab", "ab"] 와 같이 저장합니다.

 

그리고 for e in list: 를 통해 list를 순회하며

 

앞에 나온 것과 계속 같은 것이 나온다면

나온 횟수를 저장하고,

 

다른 것이 나온다면

저장된 횟수만큼 압축 문자열에 추가해주면 됩니다.

 

list = ["ab", "ab", "cd", "cd", "ab", "ab"] 와 같은 경우에 진행되는 과정은 다음과 같습니다.

1. ab, 나온 횟수는 1입니다.

2. ab, 앞에것과 같으므로 나온 횟수를 2로 증가시킵니다.

3. cd, 앞에것과 다르므로 "2ab"를 압축 문자열에 추가합니다. 나온 횟수를 1로 바꿔줍니다.

4. cd, 앞에것과 같으므로 나온 횟수를 2로 증가시킵니다.

5. ab, 앞에것과 다르므로 "2cd"를 압축 문자열에 추가합니다. 나온 횟수를 1로 바꿔줍니다.

6. ab, 앞에것과 같으므로 나온 횟수를 2로 증가시킵니다.

7. 순회가 끝나고 마지막으로 저장된 2ab를 압축 문자열에 추가합니다.

 

이렇게 압축 문자열을 구하고 나면, len(압축문자열)을 리턴해주면 됩니다.

---

def solution(s):
    least_length = len(s)
    temp = 0
    for i in range(1, len(s)//2 + 1):
        temp = zip(i, s)
        if temp < least_length:
            least_length = temp
            
    return least_length
        
        
        
def zip(num, s):
    i = 0
    zip_list = []
    while True:
        if i+num > len(s):
            zip_list.append(s[i:])
            break
        else:
            zip_list.append(s[i:i+num])
        i = i+num
    
    my_zip = ""
    before = zip_list[0]
    count = 1
    for i in range(1, len(zip_list)):
        curr = zip_list[i]
        if curr == before:
            count += 1
        else:
            if count == 1:
                my_zip = my_zip + before
            else:
                my_zip = my_zip + str(count) + before
            count = 1
        before = curr
    my_zip = my_zip + before

        
    return len(my_zip)