📌 프로그래머스 [문자열 압축]
🔗 문제 링크
문제 설명 📄
주어진 문자열 s를 일정한 길이(i)로 잘라서 압축했을 때,
가장 짧은 길이로 표현되는 결과를 찾아야 한다.
같은 문자가 연속되면 개수를 붙여서 압축한다.
문제 접근 방식 💡
- 1부터 len(s) // 2까지의 길이(i)로 문자열을 압축해본다.
- 잘린 문자열을 비교하며 중복 개수를 체크하고 압축.
- 압축된 길이를 비교하여 최소값을 찾는다.
Solution 💻
def solution(s):
if len(s) == 1:
return 1
answer = float('inf')
for i in range(1, len(s) // 2 + 1):
result = 0
before = s[:i]
count = 1
for j in range(i, len(s), i):
current = s[j:j + i]
if before == current:
count += 1
else:
result += len(before) + (len(str(count)) if count > 1 else 0)
before = current
count = 1
result += len(before) + (len(str(count)) if count > 1 else 0)
answer = min(answer, result)
return answer
시간 복잡도 분석 ⏲️
- 시간 복잡도: O(n^2)
- 길이 i만큼 문자열을 나누고 순회하는 연산 수행.
- 공간 복잡도: O(1)
- 별도의 리스트(tokens 등)를 사용하지 않아 공간 절약.
리팩토링 🛠️
def solution(s):
if len(s) == 1:
return 1
return min(
sum(len(prev) + (len(str(cnt)) if cnt > 1 else 0)
for prev, cnt in zip(
[s[j:j + i] for j in range(0, len(s), i)],
[len(list(group)) for _, group in __import__("itertools").groupby([s[j:j + i] for j in range(0, len(s), i)])]
)
) for i in range(1, len(s) // 2 + 1)
)
시간 복잡도 분석 ⏲️
- 시간 복잡도: O(n^2)
- 압축 과정에서 groupby() 사용으로 반복이 줄어듦.
- 공간 복잡도: O(n)
- 리스트 컴프리헨션 사용으로 공간 사용이 늘어날 수 있음.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
프로그래머스 [[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지] (0) | 2025.03.04 |
---|---|
프로그래머스 [후보 키] (0) | 2025.03.04 |
프로그래머스 [거리두기 확인하기] (0) | 2025.03.01 |
프로그래머스 [서버 증설 횟수] (0) | 2025.03.01 |
프로그래머스 [디펜스 게임] (0) | 2025.02.19 |