443. String Compression

String Compression - LeetCode

문자 배열 chars가 주어집니다.다음 알고리즘을 사용하여 문자 배열을 압축하세요.
1. 빈 문자열 s로 시작합니다. chars의 연속된 반복 문자 그룹마다 다음 작업을 수행합니다:
 - 그룹의 길이가 1인 경우, 문자를 s에 추가합니다.
- 그룹의 길이가 1보다 큰 경우, 문자 뒤에 그룹의 길이를 추가합니다.
2. 압축된 문자열 s는 별도로 반환하지 않고, 대신에 입력 문자 배열 chars에 저장합니다. 길이가 10 이상인 그룹의 경우, chars 배열 내에서 여러 문자로 분할될 것입니다.
3. 입력 배열을 수정한 후에, 배열의 새로운 길이를 반환하세요.
4. 상수 공간만을 사용하는 알고리즘을 작성해야 합니다.

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.

 

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

문제 요약: 

주어진 문자 배열을 위의 압축 알고리즘을 사용하여 수정하고, 배열의 새로운 길이를 반환해야 합니다.

풀이 과정:

1. 압축한 결과를 저장할 배열 output을 초기화하고, 초기 count 값을 1로 설정합니다.
2. 배열을 순회하며 현재 문자와 다음 문자가 같은 경우, count를 증가시킵니다.
3. 현재 문자와 다음 문자가 다르면, 현재 문자를 output에 추가하고 count를 문자로 변환하여 output에 추가합니다.
4. 배열 순회가 끝나면 output의 길이를 확인하여 chars 배열의 내용을 갱신합니다.
5. 배열의 새로운 길이를 반환합니다.

class Solution {
    public int compress(char[] chars) {
        int outputIndex = 0;
        int count = 1;

        for (int i = 0; i < chars.length; i++) {
            if (i < chars.length - 1 && chars[i] == chars[i + 1]) {
                count++;
            } else {
                chars[outputIndex++] = chars[i];
                if (count > 1) {
                    for (char c : String.valueOf(count).toCharArray()) {
                        chars[outputIndex++] = c;
                    }
                }
                count = 1;
            }
        }

        return outputIndex;
    }
}

 

그냥...  Input 된 chars 에 계산하면서 바로바로 output 데이터를 작성하는데

머리가 나빠... 힘들다.

char, int 를 각각 세서 저장한다음

출력용 데이터 추출하는게 편한걸 어찌하리오~

class Solution {
    public int compress(char[] chars) {
        ArrayList<Character> arrC = new ArrayList<>();
        ArrayList<Integer> arrI = new ArrayList<>();
        
        char bChar = chars[0];
        int cCnt = 0;

        for(char _char : chars){
            if(bChar == _char){
                cCnt++;
            }else{
                arrC.add(bChar);
                arrI.add(cCnt);

                bChar = _char;
                cCnt = 1;
            }
        }

        if(bChar == chars[chars.length -1]){
            arrC.add(bChar);
            arrI.add(cCnt);
        }

        String retStr = "";
        for(int i = 0; i < arrC.size(); i++){
            retStr += arrC.get(i);
            int tmpCnt = arrI.get(i);
            if(tmpCnt > 1) {
                retStr += tmpCnt;
            }
        }
        char[] arrChar = retStr.toCharArray();
        for(int i = 0; i < retStr.length(); i++){
            chars[i] = arrChar[i];
        }

        return retStr.length();
    }
}