2020 카카오공채 문자열 압축

eprj453·2020년 3월 20일
0

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

문자열을 잘라 비교하는 문제입니다.
문자열의 길이에 따라 다음과 같이 비교하며 비교하는 최대 길이는 문자열 길이의 절반입니다.


중점으로 보아야 할 부분은 두가지입니다.
  1. 기준 문자열과 비교하는 문자열이 같을때와 다를때 각각의 처리

  2. 다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다. - 문제 中

    위와 같이 남는 문자열이 남을때의 처리입니다.

Python

전체 코드입니다.

def solution(s):
    s_len = len(s)
    answer = s_len
    end = (s_len // 2) + 1
    for i in range(1, end):
        string = ""
        num = 1
        first = s[0:i]
        for j in range(i, s_len+i, i):
            compare = s[j:j+i]
            if len(first) != len(compare):
                if first == compare:
                    num += 1
                if num > 1:
                    string += str(num)
                string += first
                if compare != "":
                    string += compare
                break

            if first == compare:
                num += 1
            else:
                if num > 1:
                    string += (str(num) + first)
                else:
                    string += first
                first = compare
                num = 1
            first = s[j:j+i]

        answer = min(len(string), answer)
    return answer

단락마다 끊어서 보겠습니다.

  • 문자열의 길이를 s_len에 저장하고, 최소값을 저장하기 위해 최대 문자열의 길이를 answer에 저장합니다.
  • 비교하는 문자열의 길이는 문자열 길이(s_len)의 절반을 넘어갈 수 없으므로 반복문의 끝을 문자열 길이의 절반으로 정합니다.
def solution(s):
    s_len = len(s)
    answer = s_len
    end = (s_len // 2) + 1

  • 비교할 문자열 길이를 정할 큰 반복문입니다. i가 비교할 문자열의 길이를 나타냅니다.

  • 문자열은 최소 길이가 1이므로 num은 1로 초기화합니다. 만약 비교하면서 같은 문자열을 찾는다면 num을 늘려나가며 압축숫자를 늘려갑니다.

  • 가장 처음 기준이 될 문자열은 첫번째 문자열부터 i까지 슬라이싱한 문자열입니다.

    for i in range(1, end):
        string = ""
        num = 1
        first = s[0:i]

  • 순서대로 문자열을 비교합니다. 비교하는 문자열은 compare에 저장합니다. 문자열 비교는 i번째부터 문자열 길이에 i번째를 더한 곳까지 비교합니다. 만약 s_len까지만 비교한다면 맨 마지막 문자가 누락될 위험이 있습니다.
  • 제일 처음으로 남는 문자열이 생기는 경우를 비교합니다(if len(first) != len(compare)). 남는 문자열이 생기는 경우는 그 뒤로는 비교할 필요가 없습니다.
  • 남는 문자열이 생겼을때, 기존 문자열이 압축되고 있는 상태라면(num이 1보다 크다면) 기준 문자열은 압축한 상태로 string 변수에 붙입니다.
  • 만약 비교할 문자열이 있는 경우에는 그 문자열도 붙여준 뒤 반복문을 탈출합니다.
for j in range(i, s_len+i, i):
            compare = s[j:j+i]
            if len(first) != len(compare):
                if num > 1:
                    string += str(num)
                string += first
                if compare != "":
                    string += compare
                break

  • 만약 기준 문자열과 비교 문자열이 같다면 압축갯수를 1 추가합니다.(num += 1)
  • 문자열이 다르다면 여태까지 압축했던 문자열(num + first)을 전부 string 변수에 붙입니다.
    • 압축이 1회 이상 되었다면(if num > 1) 숫자도 함께, 압축된 적이 없으면(else) 기준 문자열만을 붙입니다.
  • 기준 문자열을 비교 문자열로 변경하고, 문자열 압축횟수도 1로 초기화합니다.
  if first == compare:
        num += 1
  else:
    if num > 1:
        string += (str(num) + first)
    else:
        string += first
    first = compare
    num = 1

j 반복문이 모두 돌면 기존의 answer와 string의 길이를 비교해 작은 값을 answer에 저장합니다.

i 반복문이 모두 돌고 answer를 return하면 정답입니다.

	answer = min(len(string), answer)
return answer

느낀점

카카오 코딩테스트에서 단골로 등장하는 문자열 조작 문제입니다.

파이썬의 장점을 살려 list comprehension 등을 이용하거나 코드의 반복을 줄여 더 간결하고 가독성 좋게 짜고 싶었으나 아직까지는 역량이 많이 부족합니다.

C++을 병행하다보니 리스트 슬라이싱을 접했을때 순간 당황했습니다. 파이썬 개념을 좀 더 탄탄하게 잡아야겠습니다.

profile
안녕하세요!

0개의 댓글