[Java] Daily LeetCode Challenge 2306. Naming a Company

https://leetcode.com/problems/naming-a-company/description/

Naming a Company - LeetCode

이게 왜 Hard인지 첫 제출하고 느낀 문제

 

총 3가지로 시도했는데,

1. 모든 경우의 수를 구하기 : 시간초과

2. 앞 첫글자 + 나머지 부분 으로 분할 : 어딘지 모르게 데이터가 커질수록 값이 적게 나옴

- 두 앞 글자의 나머지 부분들이 1개라도 서로 겹치지 않으면 각각의 크기를 곱해줌

- 1개짜리 문자는 따로 계산함 

3. DP : 성공

- dp [현재 앞글자] [바꿀 수 있는 앞글자]

- 단어를 일일이 가져와서 앞글자만 바꾼 후, 회사 이름이 될 수 있는 경우만 dp[][]에 +1 해줌

- (0 <= i , j <=25 ) dp[i][j] * dp[j][i] 총합 구하기

- 강의 많이 찾아보고 알게 된 풀이

 

※ Discussion에 올라온 힌트 보고 허점을 알 수 있었다

 

 

[코드]

import java.util.*;
class Solution {
    public long distinctNames(String[] ideas) {
        HashSet<String> hs = new HashSet<>();
        for(String s : ideas)
            hs.add(s);

        // dp [원래 알파벳][바꾼 알파벳]
        int[][] dp = new int[26][26];

        for(String s : ideas){
            // 첫 글자 가져오기
            char ch1 = s.charAt(0);

            for(int i=0; i<26; i++){
                // 모든 알파벳 가져옴
                char ch2 = (char)('a'+i);

                // 첫 글자 모두 바꾸기
                String str = ch2 + s.substring(1);

                // 바꾼 단어 원래 단어에 있는지 확인 -> 없을 때(= 가능한 단어) +1 해줌
                if(!hs.contains(str))
                    dp[(int)(ch1-'a')][i]++;
            }
        }

        long ans = 0;
        for(int i=0; i<26; i++){
            for(int j=0; j<26; j++){
                ans += dp[i][j] * dp[j][i];
            }
        }


        return ans;
    }
}