String Compression

Q: 문자열 압축의 시간 복잡도는 얼마인가요?

두 포인터 순회는 스캔 인덱스가 앞으로만 이동하므로 O(n) 시간이 걸립니다. 결과 외에 인덱스 두 개만 유지하므로 추가 공간은 O(1) 입니다.

Q: 압축된 문자열이 원본보다 더 길 수 있나요?

이 버전에서는 그렇지 않습니다. 단독 문자는 한 글자로 유지되고, k ≥ 2 개의 문자가 연속되면 한 글자와 k 의 숫자로 표현되며, 길이는 절대 k 자를 넘지 않습니다. a1b1 처럼 모든 문자 뒤에 개수를 쓰는 방식은 길이가 두 배가 될 수 있습니다.

쉬움투 포인터 배열과 문자열

+10

영문자로 이루어진 문자열 s가 주어집니다. 이 문자열을 압축하세요. 연속해서 두 개 이상 같은 문자가 반복되면 해당 문자를 반복 횟수와 함께 표시하고, 한 번만 나타나는 문자는 그대로 둡니다. 따라서 aabccc는 a2bc3가 됩니다. 압축된 문자열을 반환하세요.

대문자와 소문자는 서로 다른 문자입니다. aA는 길이가 1인 두 개의 반복 구간입니다.

함수

compress(s: string) → string

sstring: 압축할 문자열, 영문자만
반환값string: 압축된 문자열에서는 각 연속 구간을 해당 문자의 뒤에 길이가 1보다 큰 경우 그 길이를 붙여 씁니다

제약 조건

1 ≤ s.length ≤ 2 × 10⁴
s에는 a부터 z까지와 A부터 Z까지의 영문자만 포함됩니다.
런 길이는 십진수로 표기되며 여러 자릿수일 수 있습니다.

예제

입력: s = "aabccc"
출력: "a2bc3"
설명: 연속된 문자는 aa, b 및 ccc입니다. 각각 a2, b(문자가 하나만 있으면 개수를 표시하지 않음), c3이 됩니다.

입력: s = "abbbbbbbbbbbb"
출력: "ab12"
설명: a 하나, 그다음 b 열두 개. 길이 12는 두 문자 1과 2로 쓰므로 결과는 ab12입니다.

입력: s = "zzZZZ"
출력: "z2Z3"
설명: 소문자 z와 대문자 Z는 서로 다른 문자이므로, 이것은 두 개가 연속된 다음 세 개가 연속된 것입니다: z2Z3.

후속 질문

반대로 해 보세요. ab12와 같은 압축된 문자열이 주어졌을 때 원래 문자열을 다시 만들어 보세요. 여러 자리 숫자로 된 반복 횟수는 어떻게 읽나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

동일한 문자가 연속되는 각 구간이 어디서 시작하고 끝나는지 찾은 다음, 그 길이를 텍스트로 작성하세요. 문자 하나로 이루어진 구간에는 개수를 표시하지 않으며, 개수는 여러 자릿수일 수 있습니다. 인덱스 두 개를 사용하면 한 번의 순회로 처리할 수 있습니다. 하나는 구간의 시작에 두고, 다른 하나는 구간의 끝까지 이동합니다.

실행 결과를 모은 다음 작성하세요

핵심 아이디어

먼저 연속 구간을 문자와 길이의 쌍으로 기록하세요. 예를 들어 aabccc는 (a, 2), (b, 1), (c, 3)입니다. 각 문자는 마지막 연속 구간을 늘리거나 새 연속 구간을 시작합니다. 그런 다음 각 연속 구간의 문자를 쓰고, 길이가 1보다 크면 그 뒤에 길이를 씁니다.

두 번의 순회는 모두 O(n)입니다. 서로 이웃한 문자가 일치하지 않으면 목록에 n개의 연속 구간을 담을 수 있으므로 추가 공간은 O(n)이 필요합니다.

알고리즘

빈 구간 목록을 만듭니다.
s의 각 문자에 대해: 마지막 구간의 문자가 같으면 길이에 1을 더하고, 그렇지 않으면 길이가 1인 새 구간을 추가합니다.
각 구간에 대해 문자를 쓰고, 길이가 1보다 크면 그 뒤에 길이를 10진수 텍스트로 씁니다.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

각 연속 구간을 훑는 두 포인터

핵심 아이디어

현재 연속 구간의 첫 글자에 i를 두고, s[j]가 s[i]와 같을 동안 j를 앞으로 이동합니다. j가 다른 글자를 만나거나 문자열의 끝에 도달해 멈추면, 연속 구간의 길이는 j-i입니다. 이를 출력하고 i = j로 설정합니다. abbbbbbbbbbbb에서는 j가 처음에는 1에서 멈춰 a를 만들고, 그다음에는 13에서 멈춰 b12를 만듭니다.

내부 루프가 문자열의 끝에서 멈추므로 마지막 연속 구간을 위한 특별 처리는 필요하지 않습니다. j는 앞으로만 이동하므로 시간 복잡도는 O(n)이고, 결과 외에 인덱스 두 개만 유지합니다. R 및 Swift 버전은 먼저 s를 문자 배열로 분리하므로 추가 공간 O(n)을 사용합니다.

알고리즘

i = 0으로 설정합니다.
i가 문자열 안에 있는 동안 j = i로 설정하고, 문자열 안에 있고 s[j]가 s[i]와 같은 동안 j를 앞으로 이동합니다.
s[i]를 씁니다. j-i가 1보다 크면 십진수 텍스트로 씁니다.
i = j로 설정하고 반복합니다.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

함정과 경계 사례

다른 문자를 만날 때만 연속된 문자 묶음을 기록하는 경우. aabccc의 마지막 ccc 뒤에는 아무것도 없으므로 a2b를 반환합니다.
개수를 '0' + count처럼 한 문자로 기록하는 경우. 10에서 문제가 생깁니다. b가 열두 개라면 12라는 두 문자가 필요합니다.
문자가 하나만 있을 때 뒤에 1을 붙이는 경우. b는 b1이 아니라 b로 유지됩니다.
대소문자를 무시하는 경우. zzZZZ는 z5가 아니라 z2Z3입니다.
Java나 C#에서처럼 불변 문자열에 +를 사용해 문자열을 계속 이어 붙이는 경우. 각 +는 지금까지의 결과를 복사하므로 반복문이 O(n²)이 됩니다. 문자열 빌더를 사용하세요.

자주 묻는 질문3

문자열 압축의 시간 복잡도는 얼마인가요?

두 포인터 순회는 스캔 인덱스가 앞으로만 이동하므로 O(n) 시간이 걸립니다. 결과 외에 인덱스 두 개만 유지하므로 추가 공간은 O(1)입니다.

압축된 문자열이 원본보다 더 길 수 있나요?

이 버전에서는 그렇지 않습니다. 단독 문자는 한 글자로 유지되고, k ≥ 2개의 문자가 연속되면 한 글자와 k의 숫자로 표현되며, 길이는 절대 k자를 넘지 않습니다. a1b1처럼 모든 문자 뒤에 개수를 쓰는 방식은 길이가 두 배가 될 수 있습니다.

문자열을 제자리에서 압축하려면 어떻게 해야 하나요?

읽기 인덱스와 쓰기 인덱스가 있는 문자 배열을 사용하세요. 읽기 인덱스로 각 연속 구간을 스캔한 다음, 해당 문자를 쓰고 그 길이를 쓰기 인덱스에 숫자로 기록하세요. 출력 길이는 지금까지 읽은 입력보다 길어지지 않으므로 쓰기 인덱스가 읽기 인덱스를 앞지르지 않습니다. 마지막에 새로운 길이를 반환하세요.

def compress(s):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

s = "aabccc"

예상 출력

"a2bc3"