[프로그래머스] 파이썬 _ 문자열 압축 (2020 KAKAO BLIND) ⭕️

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

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

 

문제유형 : 문자열, 구현

 

공식사이트에 나와있는 출제의도 :

• 문자열을 다룰 수 있고, 아래 예시와 같이 문자열과 관련된 다양한 작업을 할 수 있는지 파악
  • 문자열 자르기
  • 부분 문자열 얻기
  • 문자열 비교하기
  • 문자열 길이 얻기

 

문제풀이 : 

 

• 우선 이 문제는 문자열의 길이가 최대 1000이므로 모든 가능한 압축을 전부 해보는 완전탐색문제이다.

 

• 길이가 줄어들수있는 최대 압축길이는 전체문자열의 반이므로 압축을 1~전체문자열길이/2 로 완전탐색한다.

 

• 나는 문자열을 압축할 길이에 맞게 나누어 배열로 만든다음 해당 배열을 돌면서 연속해서 나오는 원소가 있으면 압축하는 식으로 풀었다.
  • 현재원소와 다음 원소를 비교한다. ( 이때 리스트 인덱스를 넘어가지않기위해 반복문의 범위는 배열길이-1 로 설정한다.)
  • 현재원소와 다음원소가 다르면
    • count가 1이상이면 해당값만큼 붙여준다 (압축이 되었다는것)
    • 현재원소를 붙인다. ( 압출될일이 없음)
    • count를 1로 초기화시킨다. ( 다음압축률을 기다려야하므로 )
  • 현재원소와 다음원소가 같으면
    • count를 1 증가시킨다.
  • 해당 배열을 모두 돌았을때 계속해서 같은값이 이어져서 현재원소와 다음원소가 다른상황이발생하지않고 종료되었을때
    • count가 1이상이면 해당값만큼 붙여준다 (압축이 되었다는것)
    • 다음원소(마지막원소)를 붙인다. ( 압출될일이 없음)

 

 

정답코드 :

 

가장 최근풀이, 3번이나 풀엇다 ㅋㅋ (210824)

def solution(s):
    n = len(s)
    
    # 1부터 n을 기준으로 자를수 있고 전부 다 해본다.
    answer = n
    # i로 압축
    for i in range(1, (n//2)+1):
        divied_str = divide(s, i)
        answer = min(answer, pressing(divied_str))
        
    return answer

def divide(s, size):
    string = []
    for i in range(0,len(s),size):
        string.append(s[i:i+size])
    return string

def pressing(target):
    result = ''
    count = 1
    before = target[0]
    for t in target[1:]:
        if t==before:
            count +=1
        else:
            if count > 1:
                result += str(count)
                result += before
                count = 1
            else:
                result += before
                count = 1
        before = t
    if count > 1:
        result += str(count)
        result += before
    else:
        result += before
    
    return len(result)

 

맨처음 푼 풀이 

def solution(s):
    answer = 0
    result = len(s)
    # 자르는 길이가 1~전체길이의 절반까지 모두탐색
    for length in range(1, len(s)//2+1):
        str_list = []

        for i in range(0,len(s),length):
            str_list.append(s[i:i+length])

        answer = ''
        count = 1

        for j in range(len(str_list)-1):
            # 현재와 다음것이 다르면
            if str_list[j] != str_list[j+1]:
                if count > 1:
                    answer += str(count)
                answer += str_list[j]
                count = 1
            else:
                count += 1
        else: # 전체 반복문을 다 돌았을때 
            if count >1:
                answer += str(count)
            answer += str_list[j+1] # 여기서는 j가 아니고 j+1로 마지막원소를 붙여줘야함
        print(answer)
        result = min(result, len(answer))

    return result

solution('abcabcdede')

 

정답코드2 (210706)

def solution(s):
    result = len(s)
    max_len = result//2
    # 1부터 전체문자열길이의 반까지 전부 다 잘라본다.
    for i in range(1, max_len+1):
        #i길이로 문자열을 잘랐을때 리스트를 돌면서, 이전과 같은지 체크해가면서 
        # 이전것을 저장, 현재것과 비교했을때 현재와 다르면 숫자를 붙이고이전문자를 붙인다.
        count = 0
        before = ''
        answer = ''
        for idx, word in enumerate(split(s, i)):
            if before != word:
                if idx == 0:
                    before = word
                    count+=1
                    continue
                if count>1: answer += str(count)
                answer += before
                before = word
                count = 1
            else:
                count +=1
        if count>1:
            answer += str(count)
        answer += before
        result = min(result, len(answer))
        
    return result

# 특정문자열을 n길이로 조각내는함수 
def split(string, n):
    result = []
    for i in range(0, len(string), n):
        result.append(string[i:i+n])
    return result

 

사실 이문제는 이전에 풀었던 문제인데, 이전에 내가 작성한코드를 내가봐도 이해가 안가게 짰었다..

 

다시푸니 훨씬 가독성높은 코드로 푼것을 보니 나름 뿌듯했다 🎅🏻