알고리즘] 1

친구가 준 문제.. ( 회사 시험... )

 

다음 열의 정수 배열은 다음처럼, 현재 열의 각 정수와 그 정수가 연속적으로 나타나는 개수의 쌍으로 구성된다.
1
1 1 → 위의 열은, 1이 하나다.
1 2 → 위의 열은, 1이 두 개다.
1 1 2 1 → 위의 열은, 1이 하나, 2가 두 개다.
1 2 2 1 1 1 → 위의 열은, 1이 두 개, 2가 하나, 1이 하나다.
1 1 2 2 1 3 → 위의 열은, 1이 하나, 2가 두 개, 1이 세 개다.
1 2 2 2 1 1 3 1 → ...
1 1 2 3 1 2 3 1 1 1 → ...
…

0으로 시작하는 주어진 인덱스 M에 대해서,
M을 각 열의 인덱스라고 하자.
인덱스 M이 가리키는 열의 정수 배열은 무엇인가?

예를 들어,
만일 M=4 라면,
답은 "1 2 2 1 1 1"이다

 

 

C# 구현. ( 1시간 걸림. 삽질 30분후에 뭔가 안맞는것 같아 고민 하던 중에... )

 

            List<int> result = new List<int>();
            int[] prms = new int[] { 1 };
            int x = 0;
            int M = 5;
            for (int loop = 0; loop < M; loop++)
            {
                x = 0;
                for (int idx = 0; idx < prms.Length; idx++)
                {
                    if (x != prms[idx])
                    {
                        result.Add(prms[idx]);
                        result.Add(1);
                        x = prms[idx];
                    }
                    else
                        result[result.Count - 1]++;
                }

                textBox1.AppendText("" + loop + "] " + string.Join(" ", prms) + Environment.NewLine);

                prms = result.ToArray();
                result.Clear(); 
            }