카카오 블라인드 채용

[카카오] 2020 KAKAO BLIND RECRUITMENT 1차 풀이 – 문자열 압축

이 포스팅에서는 2020 카카오 블라인드 채용 1차 문제인 ‘문자열 압축’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/60057에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.

공식 풀이는 링크를 참조하시기 바랍니다.


문자열 압축

출처 : 2020 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/60057
카테고리 : Backtracking
난이도 : 쉬움


문제 요약

문자열이 주어질 때 임의의 단위 N으로 압축하여 만들어지는 최소 길이 문자열의 길이를 리턴하여라. 압축 단위 N은 1 ~ 문자열의 길이가 가능하다.

예를 들어 abcabcddab를 길이 3으로 압축하면 abc abc dda b에서 abc가 2개, dda는 하나 그리고 b가 하나이므로 2abcddab로 길이는 8이 된다.


문제 풀이

  • 초기의 정답은 압축하지 않은 상태의 길이인 len(text)로 둔다.
  • 압축 단위가 len(text)의 절반보다 클 때는 압축한 결과가 무조건 원래 길이보다 크기 때문에 수행할 필요가 없다. 따라서 [1, len(text) // 2] 구간의 압축 단위에 대해서만 압축을 수행한다.
  • 가능한 압축 단위에 대해 아래를 반복한다.
    • 누적 길이를 0으로 초기화한다.
    • 초기 인덱스 idx = 0으로 설정하고, idx < len(text)인 조건에서 아래를 반복한다
      • text의 idx 위치에서 압축 단위만큼 문자열을 자른다. 만약 남은 길이가 모자라면 모자란 만큼만 잘라 token에 저장한다.
      • token이 text에서 몇 번이나 반복되는지 센다.
      • token의 길이를 누적 길이에 더한다.
      • 반복 횟수가 1보다 크면 압축할 필요가 있으므로 반복 횟수의 길이도 누적 길이에 더한다.
    • 누적 길이가 현재 정답보다 작은 값이면 현재 정답을 갱신한다.
  • 정답을 리턴한다.

정답 코드

def solution(s):
min_len = len(s)
for i in range(1, len(s) // 2 + 1):
length = 0
prev = “”
idx = 0
while idx < len(s):
token = s[idx:min(idx+i, len(s))]
idx += len(token)
cnt = 1
length += len(token)
while idx + i <= len(s) and token == s[idx:idx + i]:
idx += i
cnt += 1
if cnt > 1:
length += len(str(cnt))
if length < min_len:
min_len = length
return min_len
cs

Competition 카카오 블라인드 채용 문자열 압축

admin

Recent Posts

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

3일 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

3주 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

2개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

2개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

2개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

This website uses cookies.