[프로그래머스] 삼각달팽이

문제 요약

• 달팽이의 크기 n이 주어집니다.
• 달팽이는 삼각형 모양으로 숫자가 증가하는 구조를 갖고 있습니다.
• 달팽이를 1차원 벡터로 반환하세요.
  

풀이

linear하게 달팽이의 모양대로 훑으며 연속된 숫자를 채우면 되겠다는 생각을 했다.

문제점 : 각 변마다 함수 호출

처음 디자인한 방법은 방법은 왼쪽을 채우는 함수, 아랫쪽을 채우는 함수, 오른쪽을 채우는 함수를 각각 선언하고 왼쪽이 아래를 아래가 오른쪽을 오른쪽이 결국 왼쪽을 다시 선언하는 재귀적인 방법이었다.

재귀가 너무 쌓여있는 게 문제인가 싶어서 재귀가 3단계 이상으로 가지 않게 아래처럼 바꿔보기도 했다.(어차피 재귀 1회 할 때 스택에 넣고 새로운 함수를 호출하는 시간은 동일한데 왜 굳이 이렇게 했는지..)

pair<int,int> fill_left(int si, int j){
    if(check_fill(si, j)) return pair<int,int>(0,0);
    int i;
    for(i = si;i<n&&arr[i][j]==0;i++){
        arr[i][j] = v++;
    }
    return fill_bot(i-1,j+1);
}

pair<int,int> fill_bot(int i, int sj){
    if(check_fill(i, sj)) return pair<int,int>(0,0);
    int j;
    for(j = sj;j<n&&arr[i][j]==0;j++){
        arr[i][j] = v++;
    }
    return fill_right(i-1, j-2);
}
pair<int,int> fill_right(int si, int sj){
    if(check_fill(si, sj)) return pair<int,int>(0,0);
    int i; int j = sj;
    for(i = si;i>=0&&arr[i][j]==0;i--){
        arr[i][j--] = v++;
    }
    //cout<<"fill right i j  :"<<i<<","<<j<<endl;
    return pair<int,int>(i+2, j+1);
    
}

문제는 함수호출이 너무 잦아서 호출을 할 때 엄마함수를 저장하고 자식함수를 만드는 과정, 자식함수가 끝났을 때 자식을 종료하고 엄마함수를 다시 로드하는 과정이 너무 많이 생겨서 였던 거 같다. 알고리즘적으로는 O(n)인 풀이지만 함수호출과정에서 O(3*생성되는 삼각형의 수)만큼 비용이 발생한다.

대안

메인함수에서 채우는 값만 바꿔가는 1차원 루프를 만들고 함수 호출은 하지 않는다

삽질

함수 호출과 복귀가 너무 오래걸리는 문제인줄을 파악을 못하고 벡터 push_back을 하면서 벡터가 점진적으로 확장되는 데 생긴 비용때문인가 생각을 했다...

남의 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    int arr[1001][1001] = {0, };
    int x = 0, y = 0, state = 0, num = 1;
    
    for(int i = 0; i < n; i++)
    {
        switch(state)
        {
            case 0:
                for(int j = i; j < n; j++)
                    arr[x++][y] = num++;
                x--;
                y++;
                state = 1;
                break;
            case 1:
                for(int j = i; j < n; j++)
                    arr[x][y++] = num++;
                x--;
                y -= 2;
                state = 2;
                break;
            case 2:
                for(int j = i; j < n; j++)
                    arr[x--][y--] = num++;
                x += 2;
                y++;
                state = 0;
                break;
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= i; j++)
            answer.push_back(arr[i][j]);
    }
    return answer;
}