지니로그

오늘의 학습 키워드

DP

알고리즘 문제

• LeetCode Medium 1641. Count Sorted Vowel Strings
• https://leetcode.com/problems/count-sorted-vowel-strings/description/

공부한 내용

DFS

DP

• Top-Down: 큰 문제에서 작은 문제로 쪼개가면서 해결. 초기 상태로부터 점차 확장 . 재귀와 메모이제이션을 사용
• Bottom-Top: 작은 부분 문제를 해결하며 전체 문제를 해결

오늘의 회고

처음 시도 (DFS)

• 처음에 순서를 고려해서 모든 조합을 만드는 문제라고 생각해서 DFS로 구현해보려고 했다.
  • 먼저 모음 배열이 필요하다. [ a, e, i, o. u]
  • 문자열 1개일 때 a, e, i, o, u / 2개일 때 aa, ae, ai, ao, au, ee, ei, eo, eu, ii, io, iu, oo, ou, uu / ... 이렇게 조합이 됨.
  • 주어지는 n은 조합할 문자열 길이이기 때문에 조합할 문자열 수를 재귀 호출할 때마다 +1해서 종료조건을 n과 +1씩한 조합할 문자열 수(strlen)가 같아질 때라고 생각했다.
  • 종료 조건 이후에 오는 로직에 idx와 같거나 보다 큰 인덱스로 문자열을 만드는 로직이 필요했다.
  • 또한 문제 출력 조건은 조합할 수 있는 문자열 총 개수여서 카운팅이 필요했는데 나는 이 때 List에 문자열들을 담아서 List의 size로 카운트를 하려고 했더니 로직이 복잡해지면서 구현이 어려워졌다.

해결 (DFS)

• 카운팅 해결
  • count라는 클래스 전역 변수를 두고, "재귀 함수의 return;" 은 원하는 문자열을 만들어서 반환되는 의미이기 때문에 반환 바로 직전에 count를 +1 해주므로써 카운팅을 하면 된다.
• 문자열 조합 해결 
  • n = 2라고 가정한다. 
  • 문자열을 출력하지 않아도 되기 때문에 문자열이 생성됐다고 치고 카운트를 하면 된다. 이렇게 하면 List, Map 같은 문자열을 저장할 자료구조가 필요없기 때문에 성능면으로도 로직 복잡성 측면에서도 좋다고 생각한다.
  • 내가 처음에 생각한 재귀함수와 매개변수: dfs("", 0, 0)?  or dfs("", 0, 1)? ... I don't know..
    • 왜 이렇게 생각했나 되짚어보면,
    • 처음에 만든 문자열이 없으니까 ""로 시작했다. 
    • 두번째 파라미터는 추가할 모음의 인덱스(in 모음 배열)여서 0이면 a, 1이면 e 이런식이다.
    • 세번째 파라미터는 만든 문자열의 길이이다. 0으로 할지 1로 할지 고민했다.
    • strlen이 0이면 현재 만든 문자열이 없는 상태("")이고, 1이면 현재 만든 문자열 길이가 1("a")인 상태이기 때문에 결론적으로 0이 맞다.
      => strlen이 0이면, ""인 상태 > 재귀 함수 호출할 때 현재 문자열("")에 "a"를 추가하면 현재 문자열("a")
      => strlen이 1이면, "a"인 상태 > 재귀 함수 호출할 때 현재 문자열에 "a"를 추가하면 현재 문자열("aa")
  • 처음 시작 dfs(0, 0)
    • dfs(0, 0) [""] -> dfs(0, 1) ["a"] -> dfs(0, 2) ["aa"] dfs() 호출 시 만든 문자열 "a", "aa", return(카운트+1 )
    • dfs(1, 0) [""] -> dfs(1, 1) ["e"] -> dfs(1, 2) 는 "e", "ee", return(카운트+1)
    • ...
    • dfs(4, 0) [""] -> dfs(4, 1) ["u"] -> dfs(4, 2) ["uu"] -> return;(카운트+1)

DP (Dynamic Programming)

• Top-Down
• Bottom-Top

문제 풀이

1번째 방법 DFS (문자열은 생성했다 치고, 카운팅)

class Solution {
    int count;
    int n;
    char[] vowels = {'a', 'e', 'i', 'o', 'u'};

    public void dfs(int idx, int strlen) {
    	//종료 조건 => 주어진 문자열 길이와 조합한 문자열 길이가 같은 경우
        if (strlen == n) {
            count++;
            return;
        }
		
        //idx => 현재 사용할 모음의 vowels의 인덱스
        //재귀 호출 시 vowels[idx] 으로 strlen+1 길이의 문자열을 만든다.
        //ex) n=2; count=0; idx=> 이번에 사용할 모음을 가리키는 인덱스 / strlen=> 현재 만들어진 문자열 길이
        //dfs(idx, strlen) [이번에 만들 문자열]
        //dfs(0,0) [""] -> dfs(0,1) ["a"] -> dfs(0,2) ["aa"] -> return; (count = 1)
        //		   		-> dfs(1,1) ["a"] -> dfs(1,2) ["ae"] -> return;	(count = 2)
        //				-> dfs(2,1) ["a"] -> dfs(2,2) ["ai"] -> return; (count = 3)
        //				-> dfs(3,1) ["a"] -> dfs(3,2) ["ao"] -> return; (count = 4)
        //				-> dfs(4,1) ["a"] -> dfs(4,2) ["au"] -> return; (count = 5)
        //				-> return; (count = 5)
        //dfs(1,0) [""] -> dfs(1,1) ["e"] -> dfs(1,2) ["ee"] -> return;	(count = 6)
        //				->
        //				-> return; (count = 9)
       	//...
        //
        //dfs(4,0) [""] -> dfs(4,1) ["u"] -> dfs(4,2) ["uu"] return;
        //				 -> return; (count = 15)
        
        for (int i = idx; i < vowels.length; i++) {
            dfs(i, strlen+1);
        }
    }

    public int countVowelStrings(int n) {
        this.count = 0;
        this.n = n;

        dfs(0, 0);

        return count;
    }
}

2번째 방법 DFS (문자열 + 카운팅)

class Solution {
    int count = 0;
    int n;
    char[] vowels = {'a', 'e', 'i', 'o', 'u'};

    public void dfs(String current, int idx, int depth) {
    	//카운팅 + 재귀 종료 조건
        if (depth == n) {
            count++;
            return;
        }

        for (int i = idx; i < vowels.length; i++) {
            // 현재 문자열에 모음을 추가해 길이+1 된 새로 조합한 문자열 생성
            dfs(current+vowels[i], i, depth+1);
        }
    }

    public int countVowelStrings(int n) {
        this.n = n;
        dfs("", 0, 0);  // 빈 문자열로 시작
        return count;
    }
}

3번째 방법 (DP : Bottom-Top)

class Solution {
    private Map<Integer, int[]> integerMap;
    public int countVowelStrings(int n) {
        if (Objects.isNull(integerMap)) {
            integerMap = new HashMap<>();
            integerMap.put(1, new int[]{1, 1, 1, 1, 1});
        }

        if (integerMap.containsKey(n)) {
            return Arrays.stream(integerMap.get(n)).sum();
        }

        for (int i = 2; i <= n; i++) {
            int[] prev = integerMap.get(i-1);
            int[] cur = new int[5];
            for (int j = 0; j < 5; j++) {
                for (int k = j; k < 5; k++) {
                    cur[j] += prev[k];
                }
            }
            integerMap.put(i, cur);
        }
        return Arrays.stream(integerMap.get(n)).sum();
    }
}

4번째 방법 (DP : Top-Down)

class Solution {
    private int[][] memo;

    public int countVowelStrings(int n) {
        memo = new int[n + 1][6]; // n+1 for length, 6 for vowel count from 0 to 5
        return count(n, 5);
    }

    private int count(int n, int a) {
        if (n == 1) return a;
        if (a == 1) return 1;
        if (memo[n][a] != 0) return memo[n][a];

        int result = 0;
        for (int i = a; i >= 1; i--) {
            result += count(n - 1, i);
        }

        memo[n][a] = result;
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countVowelStrings(2)); // Expected output: 15
    }
}