[C#] 삼각 달팽이

프로그래머스 문제

https://school.programmers.co.kr/learn/courses/30/lessons/68645

풀이 후기

1. 공식이 있지 않을까?

한 30분 동안 메모장 열고 계산하다가, 여기에 공식 같은 건 없다는 생각이 든 건 모양이 계속 회전한다는 걸 느꼈을 때쯤이었다.

2. n층은 n+1층에 영향을 끼치지 않을까?

공식을 포기 못 하고 2차 도전, 사각형 외부는 규칙이 있을지 몰라도 내부로 들어갈수록 고려할 요소가 너무 많았다.

3. 삼각형 배열을 2개 붙이면 사격형 배열 1개가 완성되고 어떠한 규칙이 새로 생기지 않을까?

없었음.

4. 열심히 달팽이 그리기

타일 지도의 이동처럼 움직이는 건 재미없어서 고려는 안 했는데, 결국 '처음부터 달팽이를 그릴걸...' 이라는 생각이 들었다. 그래도 그냥 그리기는 아쉬워서 조금만 더 생각.

1. 피라미드 층 1개는 1개의 배열로 생각할 수 있다.
2. 배열은 중앙에서 서로 만나면서 숫자가 채워진다.
3. 그렇기에 층을 클래스로 정의하면 쓰기 편하지 않을까...
4. 층에 숫자를 넣는 순서는 스택에서 넣고 꺼내는 것 같은 느낌.

결론은 층을 클래스로 만들어서 숫자를 앞뒤 교대로 숫자를 채우게 만들고, 순서는 스택을 2개 만들어서 넣기로 결정.

class Triple
    {
        public int index; 
        public int[] array;
        public int first;
        public int last;
        public bool front;

        public Triple(int n)
        {
            index = n;
            array = new int[n];
            first = -1;
            last = n;
            front = true;
        }

        public int FillStraight(int n)
        {
            int count = 0;
            
            for (int i = first + 1; i < last; i++)
            {
                array[i] = n + i - first - 1;
                count++;
            }

            first = last - 1;

            return count;
        }

        public void FillSingle(int n)
        {
            if (front)
            {
                first++;
                array[first] = n;
                front = false;
            }
            else
            {
                last--;
                array[last] = n;
                front = true;
            }
        }

        public bool IsFull()
        {
            return first + 1 == last;
        }

        public void WriteArray(ref int[] answer)
        {
            var myIndex = index * (index - 1) / 2;
            
            for (var i = 0; i < array.Length; i++)
            {
                answer[myIndex + i] = array[i];
            }
        }
    }

앞에서 공식을 계산했다고 했는데, 시간을 미리 날려버린 덕분에 WriteArray 메소드는 구현하는데 시간이 별로 안걸렸다.

원래는 index 기준으로 정렬해서 정답 배열에 숫자를 한 개씩 쓰려고 했는데 실행 시간이 좀...

    public int[] solution(int n)
    {
        Stack<Triple> box1 = new Stack<Triple>();
        Stack<Triple> box2 = new Stack<Triple>();

        for (int i = n; i > 0; i--)
        {
            box1.Push(new Triple(i));
        }
        
        int max = n * (n + 1) / 2;
        int[] answer = new int[max];
        int lastLine = n;
        
        Stack<Triple> fullBox = box1;
        Stack<Triple> emptyBox = box2;

        for (int i = 1; i < max + 1; i++)
        {
            if (box1.Count == 0)
            {
                fullBox = box2;
                emptyBox = box1;
            }
            else if (box2.Count == 0)
            {
                fullBox = box1;
                emptyBox = box2;
            }
            
            var temp = fullBox.Pop();

            if (temp.front && lastLine == temp.index)
            {
                i += temp.FillStraight(i) - 1;
                lastLine--;
            }
            else
            {
                temp.FillSingle(i);
            }

            if (!temp.IsFull())
            {
                emptyBox.Push(temp);
            }
            else
            {
                temp.WriteArray(ref answer);
            }
        }

        return answer;
    }

가장 오래 걸렸던 부분은 해당 층의 제일 밑에 있는 층인지 체크하는 부분. 피곤해서 그런지 자꾸 위로 올라가면서 한 줄을 채우는 걸 고치느라 시간이 좀 걸렸다.

11초나 걸려도 풀었으면 된 게 아닐까.