문제풀이)프로그래머스)c#) 단어퍼즐

단어퍼즐

URL : https://programmers.co.kr/learn/courses/30/lessons/12983?language=csharp

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

단어를 조합해서 결괏값을 만드는 과정에서 가장 최소한으로 만들 수 있는 개수를 리턴하는 문제로

단어는 무한정 중복 사용이 가능하다.

직접 짠 코드로는 테스트는 다 통과했지만. 효율면에서는 많이 떨어지는 상황이 발생했다. ㅠㅠ 시간 초과는 덤.

 

맨 처음 생각한 것은 중복 관련돼서 처리하는 과정에서 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;

    }            
}

그냥 맨땅에 헤딩하는 과정에서는 동작에 관련되서는 잘 되었지만 효율적인 문제에서는 확실히 공부 좀 더하고 개선을 해야겠다. 너무 복잡하게 원리적으로 생각한 것 같다.

 

 ★★★☆☆