문제

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 n-th term of the count-and-say sequence.

제한사항

• 1 $\leq$ n $\leq$ 30

접근

풀이보단 문제 이해하는데 더 시간이 투자되었어요. n이 1일경우 "1"을 고정으로 출력한다 가정하고, n이 2일 경우 "1"을 파싱해서 1의 개수는 1개다라는 의미로 "11"을 출력, n이 3일 경우 이전 수인 2에 해당하는 문자열을 파싱해서 1의 개수는 2개다라는 의미로 "21"을 출력하는 방식으로 인자 값에 해당하는 문자열을 출력하는 문제였어요.

저는 DP 방식으로 문제를 접근하고, 이전 문자열을 저장하고 가져와서 답을 채워 넣는 방식으로 풀었습니다.

답안

package LeetCode;

public class Solution {
    public String countAndSay(int n) {
        String[] answers = new String[31];
        answers[1] = "1";
        for(int i = 2; i <= n; ++i){
            answers[i] = getValue(answers[i - 1]);
        }
        return answers[n];
    }

    private String getValue(String prevValue){
        if(prevValue.isEmpty())
            return "";

        StringBuilder ret = new StringBuilder();
        char prevChar = prevValue.charAt(0);
        for(int index = 0, count = 1; index < prevValue.length(); ++index, ++count){
            char curChar = prevValue.charAt(index);
            if(curChar != prevChar){
                ret.append("" + (count - 1) + prevChar);
                if(index >= prevValue.length() - 1) {
                    ret.append("" + 1 + curChar);
                }
                prevChar = curChar;
                count = 1;
            } else{
                if(index >= prevValue.length() - 1){
                    ret.append("" + count + prevChar);
                }
            }
        }

        return ret.toString();
    }

    public static void main(String[] args){
        System.out.println(new CountAndSay().countAndSay(5));
    }

}