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

오늘의 과제

리트코드 Medeum으로 분류된 Count Sorted Vowel Strings입니다.

 

문제의 유형은 어제에 이어 DP(Dynamic Programing)입니다.

문제

https://leetcode.com/problems/count-sorted-vowel-strings/description/

 

 

먼저 문제 요구사항 요약입니다.

 

n이 주어질 때 모음으로만 구성되고 사전순으로 정렬된 문자열의 개수를 반환하면 됩니다.

 

DP 문제에서는 이전 값을 이용할 수 있는 점화식을 찾아내는게 전부입니다.

 

아직 다른 방법은 모르고 메모지나 노트패드를 실행시켜 최소 n이 3일 때 까지 직접 구해봅니다.

(사실 이해를 못하거나 특수한 문제일 경우 패턴을 좀 더 쉽게 찾기위해 n을 그 이상까지 구하기도 합니다)

 

문제에서 알려준 n = 2일 경우와 n이 3일때를 그려봅니다.

 

n = 2

aa ae ai ao au = 5
ee ei eo eu = 4
ii io iu = 3
oo ou = 2 
u = 1

=> 5 + 4 + 3 + 2 + 1 = 15

 

n = 3

aaa aae aai aao aau aee aei aeo aeu aii aio aiu aoo aou auu = 15
eee eei eeo eeu eii eio eiu eoo eou euu = 10
iii iio iiu ioo iou iuu  = 6
ooo oou ouu  = 3
uuu = 1

=> 15 + 10 + 6 + 3 + 1 = 35

 

자세히 보시면 이전 결과값은 다음 결과값의 처음입니다.

 

5 + 4 + 3 + 2 + 1 => 다음 결과값의 처음인 15

4 + 3 + 2 + 1 => 다음 결과값의 2번인 10 ...

 

이를 dp 배열을 활용하면 다음과 같은 점화식이 완성됩니다.

 

조금 길어 보이지만 굉장히 단순합니다.

dp[n][0] = dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2] + dp[n - 1][3] + dp[n - 1][4]
dp[n][1] = dp[n - 1][1] + dp[n - 1][2] + dp[n - 1][3] + dp[n - 1][4]
dp[n][2] = dp[n - 1][2] + dp[n - 1][3] + dp[n - 1][4]
dp[n][3] = dp[n - 1][3] + dp[n - 1][4]

 

여기서 n은 입력으로 주어진 n이 아니라 현재 구해야 하는 값으로 보시면 되고

n - 1은 직전에 구한 값으로 생각하시면 됩니다.

 

즉, 현재 인덱스의 값은 이전 결과값의 현재 인덱스부터 마지막 인덱스까지의 합입니다.

 

 

코드입니다,

import java.util.*;

class Solution {
    public int countVowelStrings(int n) {
        int[] dp = new int[5];
        // 초기값으로 n = 1일 경우 셋팅
        Arrays.fill(dp, 1);
        for (int i = 0; i < n - 1; i++) {
            dp[0] += dp[1] + dp[2] + dp[3] + dp[4];
            dp[1] += dp[2] + dp[3] + dp[4];
            dp[2] += dp[3] + dp[4];
            dp[3] += dp[4];
        }
        return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
    }
}

 

배운 점

사실 이해만 빠르다면 예제로 주어진 n = 1, n = 2의 케이스만 보고 눈치챘어야 했지만

이해가 안돼 3까지 그려보고 난 후 답을 찾았습니다.

 

예전 기억으로는 아무리 많아야 dp[2]의 값까지만 셋팅해주면 모든 문제가 풀린다고 알고 있기에

앞으로도 조금 번거롭더라도 직접 써가며 구해놓고 점화식을 도출해내는 연습을 해야할 것 같습니다.

 

Accepted 후 시간 복잡도는 0ms로 양호했지만 공간 복잡도에서 중위권에 있는걸 보아하니

메모리적으로 조금 더 최적화 할 수 있는 방법이 있는 것 같습니다.

 

다만, 공간 복잡도의 경우 요즘 서버 사양들이 괴물같기에 낭비하지 않는 선에서 크게 신경쓰지 않는 추세이며,

해당 방법을 탐구하는 것 보다 한 문제라도 더 풀어보는게 코테의 핵심이니 일단은 넘어가려고 합니다.

 

 

 

오늘의 한줄평

정답 Code Sample에서 본 충격적인 코드
return (n+1)*(n+2)*(n+3)*(n+4)/24;