[코딩테스트 일지 - 99클럽] 16일차 - Iterator for Combination

코딩 테스트 준비 일지 16 일차

• 응시 사이트 : LeetCode

• 문제 : Iterator for Combination

• 난이도 : 중

• 풀이시간 : 2h 11m

Design the CombinationIterator class:

• CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.

• next() Returns the next combination of length combinationLength in lexicographical order.

• hasNext() Returns true if and only if there exists a next combination.

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

Constraints:

• 1 <= combinationLength <= characters.length <= 15

• All the characters of characters are unique.

• At most 104 calls will be made to next and hasNext.

• It is guaranteed that all calls of the function next are valid.

문제 풀이 접근

금일 문제 역시 한번에 이해하긴 어려웠다. 그도그럴게 문제형식이 오늘은 달랐다.
매일 Main 함수에 클래스 생성해서 호출하면 나와있는 그대로 수행하게하면 됐지만, 오늘은 클래스를 디자인해서 기능을 구현하는 것이었다.
뭐.. 아마 저쪽 릿코드 내부 기능엔 생성자 만들고 Next,HasNext,Next 뭐 떡칠일거같다. for문이나 이런걸로 돌렸겠지..

문제풀이의 핵심은 문제에도 기재되어 있듯이 "조합" , 조합이 제일 중요하다.
그리고 "사전적인" 이것도 제일 중요하다 < 이거 때문에 고려안해서 타임리밋 쫘라락 떴다.
난 인덱스 바꿔가면서 순서도 다 돌려서 맞는거만 쓸줄 알았지..

위 얘기가 뭐냐면 이런것이다.
APPLE 가 있고 예를 들자.
APPLE, 3 을 준다고하면

첫번째 A 선택하고 PPLE,
두번째 P 선택하고 APLE,
세번째 P 선택하고 APLE,
네번째 L 선택하고 APPE,
다섯번째 E 선택하고 APPL 다돌면 대강 뭐 아래와 같은 문자열들이 나올것이다.

APP,APL,APE,ALE,PLE,PEA,PAE,PPA,PPL,PPE 등등 이런것들이 나올텐데, 어차피 여기서 다 사전적인 의미로 정렬 어쩌구를 해버리면 APL, PAL,LPA 다 똑같은거라.. 다돌 필요는 없다.
끄냥 맨앞 인덱스 기준으로 하나잡고 DFS해버리면 다 나온다.

아무튼 이렇게 조합을 만들고, 나머지는 쉽다.
Next는 List 에 있는거 인덱스대로 뿌려주면되고, 없으면 안주면되고,
HasNext도 List에 인덱스용으로 놔둔 Int 변수가 Count 보다 높으면 False 주고 인덱스 찍을거 있으면 True 주면 끝이다.

실패한 코드

public class CombinationIterator
    {

        public List<string> list = new List<string>();
        // 메소드 

        public string originalString = string.Empty;
        public int m_iReturnIndex = 0;
        public int m_isplitLength = 0;

        public CombinationIterator(string characters, int combinationLength)
        {
            // 스트링 문자열 하나, 조합 수 

            originalString = characters;
            m_isplitLength = combinationLength;

            for (int i = 0; i < originalString.Length; ++i)
            {
                int index = i;
                List<int> InputIndex = new List<int>();
                InputIndex.Add(i);
                string combiStr = originalString[index].ToString();

                dfsCombination(combiStr, 1, InputIndex);
            }
        }

        public void dfsCombination(string combi, int depth, List<int> IndexList)
        {
            if (depth >= m_isplitLength )
            {
                char[] chars = combi.ToCharArray();
                Array.Sort(chars);
                combi = new String(chars);

                if (list.Contains(combi) == false)
                {
                    list.Add(combi);
                }

                return;
            }

            for (int i = 0; i < originalString.Length; ++i)
            {
                if (IndexList.Contains(i) == true) continue; // 이미 조합으로 만들어낸 인덱스는 만들지 않는다.

                string newString = (combi + originalString[i]);
                List<int> newInputIndex = new List<int>();
                newInputIndex.AddRange(IndexList);
                newInputIndex.Add(i);

                dfsCombination(newString, depth + 1, newInputIndex);
            }
        }

        public string Next()
        {

            if (list.Count - 1 < m_iReturnIndex)
                return "";

            string returnStr = list[m_iReturnIndex];
            ++m_iReturnIndex;

            return returnStr;
        }

        public bool HasNext()
        {

            if (list.Count <= m_iReturnIndex)
                return false;

            return true;
        }
    }

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj.Next();
 * bool param_2 = obj.HasNext();
 */

정답 작성 코드 (C#)

public class CombinationIterator
    {

        public List<string> list = new List<string>();
        // 메소드 

        public string originalString = string.Empty;
        public int m_iReturnIndex = 0;
        public int m_isplitLength = 0;

        public CombinationIterator(string characters, int combinationLength)
        {
            // 스트링 문자열 하나, 조합 수 

            originalString = characters;
            m_isplitLength = combinationLength;
            dfsCombination("" , 0);
        }

        public void dfsCombination(string combi, int start)
        {
            if (combi.Length >= m_isplitLength)
            {
                char[] chars = combi.ToCharArray();
                Array.Sort(chars);
                combi = new String(chars);

                if (list.Contains(combi) == false)
                {
                    list.Add(combi);
                }

                return;
            }

            for (int i = start; i < originalString.Length; ++i)
            {
                dfsCombination(combi + originalString[i], i+1);
            }
        }

        public string Next()
        {

            if (list.Count - 1 < m_iReturnIndex)
                return "";

            string returnStr = list[m_iReturnIndex];
            ++m_iReturnIndex;

            return returnStr;
        }

        public bool HasNext()
        {

            if (list.Count <= m_iReturnIndex)
                return false;

            return true;
        }
    }

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj.Next();
 * bool param_2 = obj.HasNext();
 */

코드 결과