[Programmers] 단어 퍼즐

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12983

코딩테스트 연습 - 단어 퍼즐

DP를 이용하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 점화식을 cache[t의 인덱스] = min(cache[t의 인덱스], cache[t의 인덱스 - 원소 길이] + 1)로 설정해줍니다.

1.1 여기서 cache[t의 인덱스]란 t의 인덱스까지의 부분 문자열을 뽑았을 때 단어 조각들의 최소 숫자입니다.

2. 이중 반복문을 통해 위 점화식을 구해줍니다.

3. cache[t의 길이]가 INF라면 문자열을 단어 조각들로 형성 못하므로 -1을 반환해주고, 그 외 케이스는 cache[t의 길이]를 반환해줍니다.

3.1 cache[t의 길이] = t의 길이까지의 부분 문자열을 이루는 단어 조각들의 최소 숫자 = t를 이루는 단어 조각들의 최소 숫자

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <set>
	using namespace std;
	const int INF = 987654321;
	const int MAX = 20000 + 1;
	int cache[MAX];
	void init(void)
	{
	for (int i = 1; i < MAX; i++)
	{
	cache[i] = INF;
	}
	}
	int solution(vector<string> strs, string t)
	{
	init();
	for (int len = 1; len <= t.length(); len++)
	{
	for (string str : strs)
	{
	int startIdx = len - str.length();
	if (startIdx < 0)
	{
	continue;
	}
	bool allSame = true;
	for (int i = 0; i < str.length(); i++)
	{
	if (t[startIdx + i] != str[i])
	{
	allSame = false;
	break;
	}
	}
	if (allSame == false)
	{
	continue;
	}
	cache[len] = min(cache[len], cache[startIdx] + 1);
	}
	}
	return cache[t.length()] == INF ? -1 : cache[t.length()];
	}
	int main(void)
	{
	vector<string> strs = { "ba", "na", "n", "a" };
	string t = "banana";
	cout << solution(strs, t) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~