99클럽 코테 스터디 19일차 TIL + [LeetCode] 1641. Count Sorted Vowel Strings/DP 동적 프로그래밍/해시맵

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

1641. Count Sorted Vowel Strings

DP 동적 프로그래밍

해시맵

 

 

 

2. 오늘의 학습 문제 

---

문제

---

 

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

 

 

코드

---

import java.util.*;
/*
1. 해시맵을 선언해 <String , Integer[]>에 < [a, e, i, o, u]에 해당하는 각 문자: 50 크기의 배열에 key 문자가 만들 수 있는 idx+1 크기 문장수>에 저장한다.
2. 문장 길이가 n일때, 각 문자(인덱스 i)가 가질 수 있는 문장의 수는, 문자~키끝까지의 각 value에서 [n-1]인덱스에 해당하는 integer의 합계다.
3. n이 1인 경우를 초기세팅하고, 2부터 n까지 작은 것부터 map을 업데이트
4. 해당하는 값을 map에서 찾아 반환
*/

class Solution {

    
    static Map<String, Integer[]> memo;  // 메모이제이션을 위한 맵
    static List<String> aeiou = Arrays.asList("a", "e", "i", "o", "u");

    public int countVowelStrings(int n) {

        memo=new HashMap<>(); //초기화

        for(String chr : aeiou){
            Integer[] valueArray = new Integer[50];
            valueArray[0]=1;
            memo.put(chr, valueArray); //초기세팅 
        }

        //System.out.println(memo.get('o'));
        
        for(int i=2 ; i<=n;i++){
            for(String chr : aeiou){
                lexicoSort(i, chr); //
            }
        }
        
        int sum=0;

        for(String chr : aeiou){
            Integer[] valueArray = memo.get(chr);
            sum+=valueArray[n-1];
        }
        return sum;
    }

    static public void lexicoSort(int n, String startChar){
        int cnt=0;
        boolean start = false;
        for( String chr : aeiou){
            if(chr.equals(startChar)){
                start=true;// 접근    
            }
            if(start){
                Integer[] valueArray = memo.get(chr); //chr의 key 값 저장
                cnt+=valueArray[n-2]; //해당하는 값 가져와 더함 
            }
        }
        Integer[] valueArray = memo.get(startChar); //startChar의 key 값 복사하여 저장
        valueArray[n-1]=cnt; // n길이일때 가질 수 있는 문장 수 저장
        memo.put(startChar,valueArray ); //맵 갱신
    }
}

 

동적 프로그래밍 문제

어제 풀은 문제에서 데여서.. 그 문제를 떠올리며 차근차근 문제를 살펴봤다. 

우선 해시맵을 떠올렸고, 각 문자는 a, e, i, o, u 에서, 다음 문자는 사전순으로 자신과 다음 문자만 올 수 있다. 역으로보면, 각 문자의 앞글자는 a~자기자신까지 올 수 있다. 

거꾸로 문제를 푼다면 재귀적으로 풀 수 있을 것 같은데, 순서대로도 for문을 통해 풀 수 있을 것 같아 순서대로 접근하기로 했다. ->순.

 

 

 

 

 

 

 

aeiou 각 문자를 키로하고, value는 int[50] 크기의 배열인 해시맵이다. * 제약사항 1 <= n <= 50 

따라서 문장의 길이가 n일때 가질 수 있는 문장 수를 n-1번째 인덱스에 저장하고, 

n번째 인덱스는 현재키~끝까지키에서의 배열[n-1]의 값의 합계다. 

예를 들어 key가 a일때 5는 a~u키의 각 배열의 [0]번째 인덱스의 값 1들의 합 1+1+1+1+1=5이다. 

e도 1+1+1+1=4로 동일 

따라서 n=3일때 a키의 배열 [2] 값은 5+4+3+2+1=15가 되겠다. 그런식으로 lexicoSort함수를 짜고 이중 for문으로 계산한다.  

3. 오늘의 회고

---

• DP문제는 작은것부터 큰 것으로(거꾸로 가는 경우), 재귀, 해시맵을 떠올려야겠다. 
• LeetCode결과에서 런타임이 길게 나왔는데, for문 말고 재귀적으로 설계하면 시간이 단축될 것이다.