99클럽 코테 스터디 17일차 TIL, DP(Count Sorted Vowel Strings)

1. 문제 정의

2. 문제 접근

dp 토픽에 속한 것이니 dp로 풀면 될 것 같다.

3. 문제 풀이

1. 규칙을 찾는다.
2.  규칙을 통해 점화식을 찾는다.
3.  정답을 도출한다.

4. 코드

- dp를 통한 풀이

class Solution {
    public int countVowelStrings(int n) {
        int a, e, i, o, u;
        a=e=i=o=u=1;

        for(int k = 1; k < n; k++){
            a = a + e + i + o + u;
            e = e + i + o + u;
            i = i + o + u;
            o = o + u;
            u = u;
        }

        return a + e + i + o + u;
    }
}

 

- dfs를 활용한 풀이

class Solution {
    int ans;
    StringBuilder sb;
    List<String> result;

    public int countVowelStrings(int n) {
        String[] strs = {"a", "e", "i", "o", "u"};
        sb = new StringBuilder();
        result = new ArrayList<>();

        dfs(n, 0, sb, strs);
        return ans;
    }

    private void dfs(int n, int nowIdx, StringBuilder sb, String[] strs) {
        if (n == sb.length()) {
            ans++;
            result.add(sb.toString());
        } else {
            for (int i = nowIdx; i < strs.length; i++) {
                sb.append(strs[i]);
                dfs(n, i, sb, strs);
                sb.delete(sb.length() - 1, sb.length());
            }
        }
    }
}

 

5. 회고

처음에는 dfs로 접근하여 문제를 풀었다. dfs로 하면 모든 경우의 수를 구하여 결과는 같았지만, 시간이 오래 걸렸다. 그래서 dp방법으로 푸는 방법을 시도했다. 같은 문제라도 어떤 방법으로 접근하느냐에 따라 시간복잡도나 공간복잡도가 크게 달라지는게 신기하다. dp는 점화식을 찾는것이 아직까지도 잘 안되는 것 같다...