[LeetCode] 38 Count and Say

Description

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

• countAndSay(1) = "1"
• countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.
  To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

For example, the saying and conversion for digit string "3322251":

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

Example 1:

Input: n = 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Constraints:

• 1 <= n <= 30
  
  

---

풀이

• 이전 단계의 숫자를 가지고 어떤 숫자가 몇 개 있는지 확인 후 새로운 숫자로 문자를 만든다.

• 우선 단계별로 생기는 값을 저장할 배열을 만든다.

• 초기값으로 n=1일 경우 배열의 인덱스가 1일 때 1을 넣어준다.

• i=n=2 부터 n이 될 때까지 for문을 돌린다.

• i=2인 경우 이전 값은 한자리 수(=1)이기 때문에 따로 개수와 숫자를 확인하여 값배열에 저장한다.

• i>=3인 경우, 이전 문자를 하나씩 쪼개 처음부터 확인한다.

• 현재 문자와 다음 문자를 비교한다.
  - 둘이 같으면 개수를 증가시키고, 현재 문자 인덱스가 마지막-1이면 값배열에 개수과 숫자를 더해 기존에 저장된 값에 더해준다.
  - 둘이 다르면 바로 값배열에 개수와 문자를 더해주고 count를 초기화 시킨다. 만약 현재 문자 인덱스가 마지막-1이면 값배열에 개수와 다음 문자를 더한다.
  

• 마지막으로 값배열의 마지막 값을 반환한다.
  
  

---

코드

class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";

        String[] resultArr = new String[n + 1];
        int count;
        String pastNum, curDigit, nextDigit;

        resultArr[1] = "1";
        for (int i = 2; i <= n; i++) {
            count = 1;
            resultArr[i] = "";
            pastNum = resultArr[i - 1];
            if (i == 2) {
                resultArr[i] += count + Character.toString(resultArr[1].charAt(0));
            }
            for (int j = 0; j < pastNum.length() - 1; j++) {
                curDigit = Character.toString(pastNum.charAt(j));
                nextDigit = Character.toString(pastNum.charAt(j + 1));
                if (curDigit.equals(nextDigit)) {
                    count++;
                    if (j == pastNum.length() - 2) {
                        resultArr[i] += count + curDigit;
                    }
                } else {
                    resultArr[i] += count + curDigit;
                    count = 1;
                    if (j == pastNum.length() - 2) {
                        resultArr[i] += count + nextDigit;
                    }
                }
            }
        }
        return resultArr[n];
    }
}