[LeetCode] 443. String Compression

문제

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group's length is 1, append the character to s.
Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

443. String Compression는 문자열 chars가 주어졌을때 문자열에 연속으로 반복되는 문자들을 그룹으로 묶어 문자 하나와 그룹의 길이로 압축하는 문제다. 즉 aaaabb인 경우 a4b2로 압축한다. 단, 추가적인 공간을 사용하면 안된다.

BCR(Best Conceivable Runtime)

chars의 모든 문자를 한 번씩은 확인해야 하기 때문에, BCR은 chars의 길이가 $N$이라고 할 때 $O(N)$이다.

풀이

본 문제는 단순히 문제의 설명에 따라 구현을 하면 된다. chars를 선형 탐색하면서 연속해서 반복으로 나타내는 문자를 나타내는 gc가 변할 때마다 압축을 진행한다. 단 이때 주의할 점은 chars의 마지막 그룹은 for 문 안에서 압축할 수 없기 때문에 for 문이 종료하고 난 뒤 따로 진행해주어야 한다. gl은 그룹의 길이를 나타낸다. 또한, 압축을 진행하는 위치를 나타내는 ci는 항상 i보다 작거나 같기 때문에 덮어쓰기가 발생하지 않는다.

class Solution {
    public int compress(char[] chars) {
        if (chars.length <= 1) return 1;
        int answer = 0;
        int gl = 0;
        int ci = 0;
        char gc = chars[0];
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == gc) gl++;
            else {
                chars[ci++] = gc;
                answer++;
                if (gl > 1) {
                    String _gl = Integer.toString(gl);
                    for (int j = 0; j < _gl.length(); j++) {
                        chars[ci++] = (char) _gl.charAt(j);
                        answer++;
                    } 
                }
                gl = 1;
                gc = chars[i];
            }
        }
        chars[ci++] = gc;
        answer++;
        if (gl > 1) {
            String _gl = Integer.toString(gl);
            for (int j = 0; j < _gl.length(); j++) {
                chars[ci++] = (char) _gl.charAt(j);
                answer++;
            } 
        }
        return answer;
    }
}

시간 복잡도는 gl이 아무리 큰 숫자여도 상수 시간에 압축을 하기 때문에 $O(N)$이다.