코딩테스트/Python
[Programmers] Level 2. 문자열 압축
swwho
2023. 1. 5. 19:42
728x90
🔗 Problem Link
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
❔Thinking
- 주어진 문자열을 1개 이상의 일정한 단위로 잘라 압축한 문자열 중, 가장 짧은 문자열의 길이를 반환한다.
💻Solution
def solution(s):
INF = int(1e9)
answer = INF
n = len(s)
for i in range(1, n+1):
tmp = ''
prev = s[:i]
cnt = 1
for idx in range(i, n, i):
now = s[idx:idx+i]
if prev == now:
cnt += 1
else:
tmp += str(cnt)+prev if cnt > 1 else prev
cnt = 1
prev = now
tmp += str(cnt)+prev if cnt > 1 else prev
if answer > len(tmp):
answer = len(tmp)
return answer
🗝️keypoint
- 문자열의 길이가 1개이상 1000개 이하이기 때문에, 모든 경우를 확인해도 시간초과가 발생하지 않는다.
- 1개 이상의 '일정한' 단위 이므로, aabbb가 aa3b 등으로 압축될 수 없다.