단어퍼즐
URL : https://programmers.co.kr/learn/courses/30/lessons/12983?language=csharp
코딩테스트 연습 - 단어 퍼즐
단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na
programmers.co.kr
단어를 조합해서 결괏값을 만드는 과정에서 가장 최소한으로 만들 수 있는 개수를 리턴하는 문제로
단어는 무한정 중복 사용이 가능하다.
직접 짠 코드로는 테스트는 다 통과했지만. 효율면에서는 많이 떨어지는 상황이 발생했다. ㅠㅠ 시간 초과는 덤.
맨 처음 생각한 것은 중복 관련돼서 처리하는 과정에서 result 값을 기준으로 substring(index , world.length)를 처리해서 들어갈 수 있는 모든 경우의 수를 구하고, index 0번(처음)이 존재하는지 검사 후 DFS로 재귀 함수로 검사처리를 진행했다.
실제 값에 대해서는 검사는 정상적으로 잘되는 것을 확인했으나, 효율적이지 못했다.
내가 작성한 코드는 다음과 같다.
using System;
using System.Collections;
using System.Collections.Generic;
public class PuzzleInfoNode
{
public PuzzleInfoNode(int _index, List<string> _list)
{
index = _index;
stringList = _list;
}
public string stringValue
{
set
{
stringList.Add(value);
}
get
{
string returnValue = "";
for (int i = 0; i < stringList.Count; i++)
{
returnValue += stringList[i];
}
return returnValue;
}
}
public int index = 0;
private List<string> stringList = new List<string>();
public List<string> cloneStringList(){
List<string> TempList = null;
if(null != stringList){
TempList = new List<string>();
for(int i = 0; i< stringList.Count;i++){
TempList.Add(stringList[i]);
}
}
return TempList;
}
public List<PuzzleInfoNode> SubNodeList = null;
}
public class PuzzleInfo
{
public string puzzle = "";
public int index = -1;
public PuzzleInfo(string _puzzle)
{
this.puzzle = _puzzle;
}
}
public class Solution {
private List<PuzzleInfo> m_PuzzleList = null;
private PuzzleInfoNode m_Node = null;
private int answer = -1;
private string m_strResult = "";
private void SetPuzzleLoop(PuzzleInfoNode _node)
{
string value = _node.stringValue;
List<string> list = _node.cloneStringList();
string debugString = "";
int count= 0;
for(int k = 0; k<list.Count;k++){
debugString +=list[k]+",";
count++;
}
if(answer != -1 && answer <= count+1){
return;
}
if (_node.index < this.m_PuzzleList.Count)
{
for (int i = _node.index; i < this.m_PuzzleList.Count; i++)
{
string addString = value + this.m_PuzzleList[i].puzzle;
int length =addString.Length;
if (length == this.m_strResult.Length && this.m_strResult.Equals(addString))
{
debugString +=this.m_PuzzleList[i].puzzle;
count++;
//Logger.LogFormat("[Complete ] : {0} :::: {1}/ count : {2}",debugString, addString, count);
if(answer == -1 || answer > count){
answer = count;
}
}
else if (length > this.m_strResult.Length)
{
}
else if (this.m_strResult.Substring(0, length).Equals(addString))
{
for (int j = length; j < this.m_PuzzleList.Count; j++)
{
if ((value.Length) > this.m_PuzzleList[j].index)
{
continue;
}
if (null == _node.SubNodeList)
{
_node.SubNodeList = new List<PuzzleInfoNode>();
}
List<string> stringList = null;
stringList = _node.cloneStringList();
if(null == stringList){
stringList = new List<string>();
stringList.Add(value);
}
else{
stringList.Add(this.m_PuzzleList[j].puzzle);
}
PuzzleInfoNode saveInfo = new PuzzleInfoNode(j, stringList );
_node.SubNodeList.Add(saveInfo);
}
}
}
if (null != _node.SubNodeList)
{
for (int i = 0; i < _node.SubNodeList.Count; i++)
{
this.SetPuzzleLoop(_node.SubNodeList[i]);
}
}
}
}
public int solution(string[] strs, string t)
{
//Logger.LogFormat("Solution Value : {0} :: result : {1}", strs, t);
this.m_strResult = t;
this.answer = -1;
this.m_PuzzleList = new List<PuzzleInfo>();
for (int i = 0; i < strs.Length; i++)
{
string value = strs[i];
int length = value.Length;
for (int j = 0; j < this.m_strResult.Length; j++)
{
if ((j + length > this.m_strResult.Length))
{
break;
}
string tempString = this.m_strResult.Substring(j, length);
if (value.Equals(tempString))
{
PuzzleInfo info = new PuzzleInfo(value);
info.index = j;
this.m_PuzzleList.Add(info);
//Logger.LogFormat("Test Value :{0} index :{1}", value, j);
//tempValue += string.Format("{0}", i + 1);
}
}
//Logger.LogFormat("Test Value :{0} divistring :{1}",value, divistring);
}
this.m_PuzzleList.Sort((info1, info2) => { return info1.index.CompareTo(info2.index); });
if (this.m_PuzzleList.Count == 0 || this.m_PuzzleList[0].index != 0)
{
return answer;
}
else
{
for (int i = 0; i < this.m_PuzzleList.Count; i++)
{
if (this.m_PuzzleList[i].index != 0)
{
continue;
}
this.m_Node = new PuzzleInfoNode(i,new List<string>(){this.m_PuzzleList[i].puzzle});
this.SetPuzzleLoop(this.m_Node);
}
}
//Logger.LogFormat("PrimeNumber Count : {0}", answer);
return answer;
}
}
다른 사람이 푼 참고할만한 코드도 첨부한다.
public class Solution
{
public int solution(string[] strs, string t)
{
int answer = 0;
int maximum = t.Length; // 찾고자 하는 문자열의 길이
int i, j, p, q;
int[] result = new int[t.Length];
for (i = 0; i < maximum; i++)
{
// 디폴트 값으로 최대값 + 1 을 설정하여 불가능한 값으로 설정
result[i] = maximum + 1;
for (j = 0; j < strs.Length; j++)
{
// 현재 위치부터 역으로 탐색하여 부분문자열이 맞는지 확인
p = strs[j].Length - 1;
for (q = 0; q < strs[j].Length; q++)
{
//Console.Write(", ");
//Console.Write(strs[j][p - q]);
if (!(p - q < 0 || i - q < 0) && strs[j][p - q] == t[i - q])
continue;
else
break;
}
// 해당 부분문자열이 모두 포함된다면, 결과값 계산
if (q == strs[j].Length)
{
// 부분문자열로 완성시키전의 최소값 + 1
if (i - q >= 0)
{
result[i] = result[i] > (1 + result[i - q]) ? (1 + result[i - q]) : result[i];
}
// 처음 부분문자열을 완성한 것이라면 1로 설정
else
{
result[i] = 1;
}
}
}
}
// 전체 정답은 문자열의 마지막 원소의 Result값
answer = result[maximum - 1];
// 만약 불가능한 값(디폴트값)이 정답이라면 불가능한 경우이므로 -1 리턴
if (answer == maximum + 1) answer = -1;
return answer;
}
}그냥 맨땅에 헤딩하는 과정에서는 동작에 관련되서는 잘 되었지만 효율적인 문제에서는 확실히 공부 좀 더하고 개선을 해야겠다. 너무 복잡하게 원리적으로 생각한 것 같다.
★★★☆☆
반응형
댓글