LeetCode Count and Say (JavaScript)

링크 : https://leetcode.com/problems/count-and-say/

문제 설명

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the run-length encoding of countAndSay(n - 1).

Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511".

Given a positive integer n, return the nth element of the count-and-say sequence.

Example 1:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

Example 2:

Input: n = 1

Output: "1"

Explanation:

This is the base case.

Constraints:

• 1 <= n <= 30

---

문제 풀이

반복문을 통한 풀이

1. 처음 반복문은 n - 1번 반복해야 하므로 범위를 0 ~ n - 1로 지정

2. 내부 반복문 로직 (현재 검사하려는 단어와, count를 계산) -> 마지막 단어까지 검사해야 하므로 범위를 answer.length + 1까지 반복

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    let answer = '1';

    for (let i = 0; i < n - 1; i++) {
        let count = 0;
        let tmp = '';
        let target = answer[0];
        for (let j = 0; j < answer.length + 1; j++) {
            if (target === answer[j]) {
                count++;
                continue;
            }

            tmp += `${count}${target}`;
            target = answer[j];
            count = 1;
        }

        if (tmp) {
            answer = tmp;
        }
    }

    return answer;
};

---

결론

반복문을 통한 풀이로 범위를 잘 지정해주면 쉽게 해결할 수 있음

-> 재귀를 통해서도 해결할 수 있음 아래 더보기 참고

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    if (n === 1) {
        return '1';
    }

    const prev = countAndSay(n - 1);

    let answer = '';
    let index = 0;

    while (index < prev.length) {
        let count = 1;
        let char = prev[index];
        let j = index + 1;

        while (j < prev.length && prev[j] === char) {
            count++;
            j++;
        }

        answer += count.toString() + char;

        index = j;
    }

    return answer;
};