[알고리즘 C++]단어 퍼즐

이로서, 프로그래머스 시스템 적응을 위한 모의테스트를 모두 마쳤다

https://programmers.co.kr/learn/courses/18/lessons/1882

오늘의 문제

단어 퍼즐

처음에 봤을 때는 모르겠어서 풀지를 못해서 결국 어떤 방법을 쓰는지만 슬쩍 봤다. DP를 이용하는것이라는 것만 알고나니 스르륵 풀려갔다. 어떤 알고리즘을 적용해야하는지에 대한 안목이 필요하다

나의 풀이

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <limits.h>
using namespace std;

int solution(vector<string> strs, string t)
{
    set<string> str_set(strs.begin(), strs.end()); // set

    const int INF = 100001;
    int len = t.size();
    int dp[20001]; 
   
    for(int i=0;i<len;i++) // 초기화
        dp[i] = INF; 
    if(str_set.find(t.substr(0, 1)) != str_set.end())
        dp[0] = 1;

    for(int i=1;i<len;i++){
        for(int j=1;j<=5;j++){
            if(i-j<-1) // 더이상 갈 수 없어
                break;
            if( str_set.find(t.substr(i-j+1, j)) != str_set.end()){ // 찾아보기
                dp[i] = min(dp[i], dp[i-j] + 1);
                if(i-j+1 == 0){
                    dp[i] = 1;
                    break;
                }
            }
        }
    }

    if(dp[len-1] == INF)
        return -1;
    return dp[len-1];
}

모범 답안

using namespace std;

int solution(vector<string> strs, string t)
{
    set<string> str_set;
    const inf INF = 987654321;
    vector<int> dy(20002, INF);
    
    int len = sentence.length();
    
    for(int i=0;i<str_array.size();i++)
    	str_set.insert(str_array[i]);
        
    dy[len] = 0;
    for(int i=len-1;i >=0;--i){
    	for(int i=0;i + j<len && j<5 ;++j)
    	{
    		tmp += sentence[i+j];
        	if(str_set.find(tmp) != str_set.end() && dy[i+j+1] != INF)
        	dy[i] = min(dy[i+j+1]+1);
    	}
	}
    if(dy[0] == INF)
    	return -1;
    return dy[0];
}

배울 점

• 이번엔 내가짠 코드가 더 헷갈리지 않게 잘 짠것 같은 느낌이다.
• 문자열문제를 풀면서 string 사용방법을 다시 공부할 수 있었고 STL의 set 템플릿을 사용해볼 수 있었다.
• JAVA가 주 언어여서 그런지 C++이 문자열 처리에서 많이 약하다고 알고있어 걱정하고 있었는데, STL 라이브러리 덕분에 비슷하게 처리가 가능한 것같아 걱정이 줄었다.
• 배우고 푸는 방법을 알아가는 과정이 즐겁다.