[LeetCode] 38. Count and Say - 깊이우선탐색(DFS) JAVA

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

코드설명

깊이우선탐색(DFS)을 활용합니다.

 

문제에 주어진대로 점화식을 세워서 해결하면 됩니다.

코드

정답코드1입니다.

class Solution {
    public String countAndSay(int n) {
        return DFS(n);
    }
 
    String DFS(int n){
        if(n == 1) return "1";
        StringBuilder ret = new StringBuilder();
 
        String A = DFS(n - 1);
        for(int i=0; i<A.length(); i++){
            int repeatCnt = 1;
            while(i + 1 < A.length() && A.charAt(i) == A.charAt(i + 1) ){
                repeatCnt += 1;
                i += 1;
            }
            ret.append(repeatCnt).append(String.valueOf(A.charAt(i)));
        }
        return ret.toString();
    }
}

 

정답코드2입니다. 처음에 작성한 코드입니다. 불필요한 변수가 많습니다.

class Solution {
    public String countAndSay(int n) {
        return DFS(n);
    }
 
    String DFS(int n){
        if(n == 1) return "1";
        StringBuilder ret = new StringBuilder();
 
        String A = DFS(n - 1);
        for(int i=0; i<A.length(); i++){
            int repeatCnt = 1;
            int idx = i;
            while(idx + 1 < A.length() && A.charAt(idx) == A.charAt(idx + 1) ){
                repeatCnt += 1;
                idx += 1;
            }
            ret.append(repeatCnt).append(String.valueOf(A.charAt(idx)));
            i = idx;
        }
        return ret.toString();
    }
}