[프로그래머스] 문자열 압축 (Python 파이썬)

2020 KAKAO BLIND RECRUITMENT LEVEL 2 문자열 압축

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60057

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

💡 아이디어

💡 문제를 어떤 방식으로 해결하려 했는지 그 과정을 적어주세요. 초기에 접근한 방법과 최종 접근이 차이가 없으면 한개만 적어도 됩니다.

초기 접근

    처음에는 단순하게 빈 문자열을 하나 생성해서 거기에 한 글자씩 더해가면서 매번 비교를 하려고 했다. 이렇게 되면 for문이 모든 글자에 대해 돌아야 하는... 그리고 비교할 때 기준이 되는 애와 비교 대상인 애를 위해 for문을 또 열심히 돌려줘야 했다. 이런 식으로 그냥 무작정 짜다가 이건 아니지! 라고 생각하고 slicing을 생각하게 되었다.

 

    그리고 문제를 꼼꼼히 읽지 못했었다. abcdef에서 두 개씩 나누게 되면 ab cd ef 이런 식인데 그냥 계속해서 서로 비교해주는 줄 알았다. ab랑 bc 비교하고, 그다음에 bc랑 cd 비교하는... 이런 문제면 대체 어떻게 풀어야되는 건가 생각하다가 문제 다시 읽고 다시 풀었음...~^^

최종 접근

    위에서 스포했듯이 slicing을 사용하였다. 우리가 python을 쓰는 이유 중 하나는 정말 다양한 자료형이 있고, 그 안에서 편리하게 자르고 붙이고 뭐하고 뭐하고 할 수 있다는 거. 나는 맨날 문제를 풀 때 아니 이걸 좀 쉽게 풀 수 있는 내장함수가 없을까, 이런 걸 생각한다. (쉽게 풀 수 있는 자료구조는 없을까 는 생각하지 않음. 생각 좀 해라...^^) 그러다보니 떠오른 게 문자열 slicing.

 

    잘리게 되는 문자열의 길이는 무조건 단위 길이(아래 코드에서의 length)가 된다. 그냥 편하게 앞 순서에 나오는 문자열을 비교 대상, 그 다음에 나오는 거를 현재 문자열이라고 하겠다. 현재 문자열은 비교 대상의 다음 위치부터 다음 위치 + length까지의 문자열이 된다. (무슨 말인지 이해가 되려나...) 아무튼 이런 식으로 현재 문자열이 시작되는 index의 위치를 비교 대상의 마지막 위치+1로 계속해서 갱신하면서 slicing을 하게 된다.

 

    아 그리고 while문을 쓰면서 제일 조심해야하는 것은 나머지 처리인 것 같다. while문의 특성 상 조건에 걸리게 되면 그냥 빠져나오게 되는데, 이럴 경우 이전에 처리하고 있던 자료들이 그냥 싹 날아가게 된다. 나는 이걸 주로 while문 밖에서 나머지 처리를 해준다. 물론 그 안에서 하는 방법도 있겠지만... 난 그냥 직관적으로 while문이 종료된 뒤에 일괄적으로 나머지 처리를 해준다.

    이 문제에서도 마찬가지로 처리하고 있던 결과를 while문 밖에서 정리를 해줬고, 그다음에 문제에서 요구한 것과 같이 남은 글자의 개수가 length보다 작아 하나의 문자열이 되지 못한 문자들을 처리해줬다.

 

뭔가 되게 지저분하게 말하고 있는 것 같긴 한데 나중에 읽었을 때 이해가 잘 됐으면 좋겠다

📋 사용 스펙

💡 어떤 알고리즘 또는 기법을 사용해 문제를 해결했는지 알려주세요

 

Python 문자열 slicing

👨🏻‍💻 👩‍💻 코드

def solution(s):
    answer = 0
    
    # 비교할 기준 길이. 제일 초기에 주어진 문자열의 길이로 설정.
    prevLen = len(s)
    
    # 잘리는 문자열이 최소 두 개 이상이어야 하기 때문에
    # 잘리는 길이를 len(s)//2까지로 제한. python range함수 특성 상 +1 해줌  
    for length in range(1, len(s)//2+1):
        # 현재 길이에서 나온 문자열 저장 위한 변수
        nowTxt = ""
        # 비교 대상이 되는 문자열 저장.
        prevWord = s[:length]
        # 다음 문자열의 시작 위치는 length부터.
        newIdx = length
        # 겹치는 개수 세어주기 위한 변수.
        # 일단 비교 대상의 단어도 하나로 포함되기 때문에 0이 아니라 1부터 시작
        cnt = 1
        
        # 새로 생성할 수 있는 length 길이의 문자열이 없을 때까지.
        while newIdx + length <= len(s):
            # 다음 문자열은 이전 문자열이 끝난 그 다음 위치에서부터
            # length의 길이를 가지게 됨. slicing 이용
            newWord = s[newIdx : newIdx+length]
            # 만약 비교 대상의 문자열과 현재의 문자열이 같을 경우
            # cnt변수 갱신
            if newWord == prevWord:
                cnt += 1
            # 다를 경우
            else:
                # 이전에 겹친 경우가 있을 때에는
                if cnt != 1:
                    # nowTxt에 cnt도 함께 집어넣어줌
                    nowTxt += str(cnt)+prevWord
                    # 비교 대상이 바뀌게 되므로 cnt값 초기화
                    cnt = 1
                # 이전에 겹친 경우가 없을 때
                else:
                    # 그냥 이전의 문자열을 넣어줌
                    nowTxt += prevWord
                # 비교 대상 갱신. 현재의 문자열로.
                prevWord = newWord
                
            # 시작 위치 변경.
            # 갱신된 비교 대상 문자열이 종료되는 위치부터 시작
            newIdx += length
        
        # 이전에 진행되던 내용이 처리되지 않고 종료되었을 때를 위한 부분
        if cnt != 1:
            nowTxt += str(cnt)+prevWord
        else:
            nowTxt += prevWord
            
        # 문자열로 만들어지지 못한 나머지 문자들을 붙여줌
        nowTxt += s[newIdx:]
        
        # 만약 새로 만든 문자열의 길이가 더 짧을 경우 길이 갱신
        if len(nowTxt) < prevLen:
            prevLen = len(nowTxt)
    
    answer = prevLen
    
    return answer

 

문제 좀 잘 읽자.

그리고 항상 느끼는 거지만 파이썬 최고.