문제 개요
하나의 문자열 s가 주어졌을 때, 이를 런 길이 인코딩(Run Length Encoding) 형태로 압축하는 프로그램을 작성해 보겠습니다.
런 길이 인코딩은 동일한 문자가 연속적으로 k번 반복될 경우, 해당 문자와 반복 횟수를 함께 표기하는 방식입니다. 예를 들어 'bbbb'는 문자 'b'가 4번 연속 나타나므로 'b4'로 인코딩됩니다. 다만, 한 번만 등장하는 문자에는 개수를 붙이지 않습니다.
예시
- 입력: s = "abbbaaaaaaccdaaab"
- 출력: ab3a6c2da3b
위 예시에서 'bbb'는 'b3', 'aaaaaa'는 'a6', 'cc'는 'c2', 'aaa'는 'a3'으로 변환되며, 한 번씩만 등장하는 'a', 'd', 'b'는 그대로 유지됩니다.
풀이 접근 방법
이 문제는 문자열을 왼쪽부터 차례대로 순회하면서 연속된 문자의 개수를 세는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- 결과를 저장할 빈 문자열 res와 카운터 cnt := 1을 초기화합니다.
- i를 1부터 (s의 길이 - 1)까지 반복합니다.
- s[i - 1]과 s[i]가 같다면 cnt를 1 증가시킵니다.
- 다르다면 s[i - 1]을 res에 추가하고, cnt가 1보다 크면 cnt도 res에 추가한 뒤 cnt를 1로 초기화합니다.
- 반복이 끝난 후 마지막 문자를 res에 추가하고, cnt가 1보다 크면 cnt도 함께 추가합니다.
- res를 반환합니다.
구현 코드
아래의 Python 코드를 통해 실제 구현을 확인할 수 있습니다.
def solve(s):
res = ""
cnt = 1
for i in range(1, len(s)):
if s[i - 1] == s[i]:
cnt += 1
else:
res = res + s[i - 1]
if cnt > 1:
res += str(cnt)
cnt = 1
res = res + s[-1]
if cnt > 1:
res += str(cnt)
return res
s = "abbbaaaaaaccdaaab"
print(solve(s))입력
"abbbaaaaaaccdaaab"
출력
ab3a6c2da3b
정리
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 연속된 문자를 묶어 표현하는 런 길이 인코딩은 데이터 압축의 가장 기본적인 형태 중 하나로, 이미지 파일 포맷인 BMP나 PNG 등에서도 유사한 원리가 활용됩니다. 문자열 처리 로직 연습 문제로도 매우 유용하니 직접 다양한 입력값으로 테스트해 보시길 권장합니다.