[LeetCode] String Compression

https://leetcode.com/problems/string-compression/description/?envType=study-plan-v2&envId=leetcode-75

 

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".

 

Constraints:

• 1 <= chars.length <= 2000
• chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

 

랜덤하게 문자열이 들어 있는 배열이 있다.

이 배열 안에서 하나의 문자열이 여러 번 반복될 경우,

반복되는 횟수를 해당 문자열 뒤에 위치하도록 하고 중복되는 문자열은 제거하여 그 배열의 길이를 리턴한다.

단, 배열을 새로 만들지 말고 파라미터로 넣어준 배열을 수정해야 한다.

그리고 두자리 이상의 횟수가 나오면 "12" 가 아니라, "1", "2"를 배열에 넣어 줘야 한다.

 

 

문제 풀이

function compress(chars) {
  let currentChar = "";
  chars.map((char, index) => {
    if (char === currentChar) {
      // 이전 문자열과 동일하면 지금 위치의 문자열을 공백처리한다.
      chars.splice(index, 1, "");
    }
    if (char !== currentChar) {
      currentChar = char;
    }
  });

  // 남은 공백을 제거하고 수를 넣는다.
  let cnt = 1;
  // index 꼬임 방지를 위해 뒤에서부터 진행한다.
  for (let i = chars.length - 1; i >= 0; i--) {
    if (chars[i] === "") {
      // 공백이면 공백을 제거하고 cnt 증가
      chars.splice(i, 1);
      cnt++;
    } else {
      // 아니면 새로운 문자열이 나타난 것. 반복횟수를 넣어준다.
      cnt > 1 && chars.splice(i + 1, 0, ...String(cnt).split(""));
      cnt = 1;
    }
  }
  return chars;
}

 

나는 일단 반복되는 문자열이 있으면 맨 처음 시작 문자열을 제외하고 공백으로 바꿔줬다.

배열을 새로 만들지 않고 수정해야 한다는 게 굉장히 까다로운 부분이었는데...

filter를 쓸 수가 없어서 정말 난처했다ㅠㅠㅋㅋㅋ 결국은 안 써도 되는 코드가 되었지만...

원래는 횟수를 세면서 문자열이 바뀌었을때 횟수를 넣어주고 filter로 공백처리된 문자열을 따로 지우려고 했기 때문에ㅎㅎ

 

아니 근데 지금 보니까 그냥 배열 새로 만들어도 상관없잖아!!!!!ㅋㅋㅋㅋㅋ 제출이랑 상관없는거였다...

 

아무튼 위 코드를 작성하면서 index 꼬이는게 제법 고민됐는데, 그냥 단순히 뒤에서부터 보면 되는 거였다. 쩝...

반복문을 두번 썼다는 게 좀 마음에 안 들지만.. 그래도 미디엄치고는 (그리고 나 치고는) 나름 빠르게 길을 찾은 것 같다.

 

 

다른 풀이

이제 다른 사람들이 작성한 해답을 한 번 보자.

 

function compress(chars: string[]): number {
    let res: number = 0;
    let i: number = 0;
    const len: number = chars.length;

    while (i < len) {
        let count = 1;

        while (i + count < len && chars[i + count] === chars[i]) {
            count++;
        }
        chars[res++] = chars[i];

        if (count > 1) {
            for (let digit of `${count}`) {
                chars[res++] = digit;
            }
        }
        i += count;
    }

    return res;
}

 

한 다섯개 정도 보니까 대부분 이중으로 반복문을 사용했던데, while을 쓴 사람이 많았다.

어차피 i++를 해줄 거라면 왜 굳이 while을 쓴걸까? 이해가 잘 안 된다.

for (let i = 0; i< ... ) 이게 너무 길어서 쓰기 싫었나? 효율이 다른가?

 

아무튼 기본적인 로직은 나와 동일한데, 여기서는 바로바로 카운트를 적어준다는 차이가 있다.

그리고 두자리수 이상의 횟수를 배열에 넣을 때, String을 for문에 넣어서 입력한 점이 인상깊었다.

String도 for문에 넣을 수 있다는 걸 알고는 있었는데 실제로 사용할 일은 평소에 없어서... 다시 머릿속에 새겨야겠다.