Word Break

요즘 들어 코딩테스트 관련해서 현타가 제대로 온거같다...진짜 취업 못했으면 아마 지금쯤 엄청난 현타가 왔을거 같아서 너무 무섭다. 내 현실에 그래도 다행이라고 생각한다. 퇴근하고 와서 한 문제라도 푸는게 목표인데 요즘은 문제를 도전하려고 하면 자꾸 답 부터 찾으려고 하는 버릇이 있는거같아서 좀 꾸준히 앉아서 열심히 해보고 노력해보고 싶다.

최근들어 DP 문제를 좀 자주 풀기는 하는데 아직도 감이 올듯 안올듯 하는거같다. 지금까지 풀었던 Stocks 문제도 다 정리해야하는데 천천히 해야곘다. 먼저, 이 문제는 wordDict 안에 있는 문자열을 사용해서 s를 나눌 수 있는지 물어보는 문제다. 원래 이 문제를 그냥 Brute Force로 풀게 된다면은 딕셔너리를 하나씩 확인하고 단어 하나씩 확인하는 번거로움이 있었을것이다. 그렇지만 DP 테이블을 이용해서 만들 수 있는 문자열에 True 값을 넣어줌으로 wordDict는 여러번 읽겠지만 결국 큰 틀에서 보면은 시간을 줄여서 런할 수 있다.

가장 처음에 dp[0] 는 true 값으로 해놓고 그 다음부터 세트를 읽을때는 substring 함수를 이용해서 wordDict의 단어 중 하나라도 만들 수 있다면 해당 문자의 위치에 True 값을 넣어주었다. 이렇게 끝까지 가게되면 결국 남는 문자열을 확인할 수 있고 답을 얻을 수 있을것이다.

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1]; 
        dp[0] = true; 
        Set<String> newSet = new HashSet<>(); 
        newSet.addAll(wordDict); 
        
        for(int i = 1; i <= s.length(); i++){
            for(String words : newSet){
                if(i < words.length()) continue; 
                if(dp[i - words.length()] && newSet.contains(s.substring(i - words.length(), i))){
                    dp[i] = true; 
                }
            }
        }
        
        
        return dp[s.length()]; 
    }
}