이코테-chapter12: 구현-문자열 압축
문제
풀이
- 문자열의 길이가 1000이하이기 때문에 가능한 모든 경우의 수를 탐색하는 완전 탐색을 수행할 수 있다.
코드
# https://programmers.co.kr/learn/courses/30/lessons/60057
# 난이도: 중, 메모리 제한: 128MB, 2020 kakao 신입 공채 기출
def solution(s: str) -> int:
answer = len(s)
# 1개 단위(step)부터 압축 단위를 늘려가며 확인
for step in range(1, len(s)//2+1):
compressed = ''
prev = s[0:step] # 앞에서부터 step만큼의 문자열 추출
count = 1
# 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
for j in range(step, len(s), step):
# 이전 상태와 동일하다면 압축 횟수(count) 증가
if prev == s[j:j+step]:
count += 1
# 다른 문자열이 나왔다면 (더 이상 압축하지 못하는 경우라면)
else:
compressed += str(count) + prev if count >= 2 else prev
prev = s[j:j+step] # 다시 상태 초기화
count = 1
# 남아 있는 문자열에 대해서 처리
compressed += str(count) + prev if count >= 2 else prev
# 만들어지는 압축 문자열이 가장 짧은 것이 정답
answer = min(answer, len(compressed))
return answer
if __name__ == '__main__':
print(solution("aabbaccc")) # 7
print(solution("ababcdcdababcdcd")) # 9
print(solution("abcabcdede")) # 8
print(solution("abcabcabcabcdededededede")) # 14
print(solution("xababcdcdababcdcd")) # 17
출처 & 깃허브
이것이 취업을 위한 코딩 테스트다 with python
github
Author And Source
이 문제에 관하여(이코테-chapter12: 구현-문자열 압축), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cosmos/이코테-chapter12-구현-문자열-압축저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)