Q09. 문자열 압축
🐣문제
문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 것이 비손실 압축 방법 중 하나입니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
- 문자가 반복되지 않아 한번만 나타난 경우 1은 생략함.
- 자르는 문자열의 길이는 일정함. (3단위로 자르다가 2단위로 자르는 등의 경우는 불가)
- 왼쪽부터 문자열 단위로 빠짐 없이 자름. (3개 단위로 자른다고 했을 때 a3bcd2abc 등의 결과 불가)
프로그래머스 링크 | https://programmers.co.kr/learn/courses/30/lessons/60057
🐥풀이
왼쪽부터 문자열을 잘라 압축하므로 최대 (문자열 길이)//2+2 길이까지 문자열 패턴 길이가 가능하다. (절반보다 크면 문자열 압축이 불가능해짐) 따라서 문자열 패턴의 길이를 1부터 (문자열 길이)//2+2까지 판단해서 최소를 구해야 한다.
패턴의 길이를 정했으면, 문자열 압축을 실행한다.
1. 한 변수에 패턴의 길이만큼 잘라서 문자열 패턴을 저장한다.
2. 패턴 길이만큼 건너뛰면서 특정 문자열과 변수에 저장된 패턴을 비교한다.
3. 문자열과 변수가 일치하면, 개수 변수를 +1 증가시킨다. (7에서 계속)
4. 일치하지 않으면, 개수 변수의 값을 확인한다.
5. 개수 변수의 값이 1이면, 결과 문자열에 변수에 저장된 패턴을 그냥 더한다. (1은 생략하므로)
6. 개수 변수의 값이 1보다 크면, 결과 문자열에 str(개수 변수)+(변수에 저장된 패턴)을 더한다.
7. 변수에 일치하지 않은 특정 문자열로 업데이트 하고, 개수 변수는 1로 초기화한다.
해당 범위의 문자열 압축이 끝났으면, 다른 범위의 문자열 압축 후의 결과 문자열 길이와 비교해서 최솟값을 저장한다. (문자열 길이)//2+2까지 모든 범위를 돈 후에는 최솟값을 반환한다.
🐓코드
def solution(s):
size = 1001 # 문자열 길이는 1000까지이므로
# 자르는 문자열 단위 길이
for i in range(1,len(s)//2+2):
# 압축한 문자열 결과, 단위 개수, 현재 문자열 단위
result, count, temp = '', 1, s[:i]
# 패턴의 길이인 i만큼 건너뛰면서 패턴 일치 판단
for j in range(i, len(s)+i, i):
if temp==s[j:j+i]:
count += 1
else:
if count==1:
result += temp
else:
result += str(count)+temp
temp= s[j:j+i]
count = 1
size = min(size, len(result))
return size⭐2022.04.04
스터디를 하는 당시에도 문제 이해가 어려웠었다. 문제 이해만 되면 조금만 머리 써서 풀 수 있는 문제 :) 카카오 코테 문제는 기본적으로 귀여운 캐릭터 그림이 있는 문제면 거르라고 들었다.. ㅎㅁㅎ (메모메모) 이 문제는 캐릭터 그림은 없었어서 문제 이해만 잘하면 무난무난!
