삼각 달팽이

코드

[ 나의 풀이 ] - 직관적인 풀이

#include <string>
#include <vector>
// 01:07 시작 ~ 02:53 종료
using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    vector<vector<int>> set(n);
    vector<pair<int,int>> ht(n); // head-tail
    int untill = (n*(n+1))/2;

    /* head-tail 값 지정 & 해당 배열 크기 생성  - 그냥 resize()로 공간만 했어도 됬네요ㅎㅎ */
    for(int j=1,i=0,idx=0;j<=n;j++)
    {  
        int cnt=0;
        ht[idx] = {0,0};
        while(j != cnt)
        {
            // 들어가는 값은 사실 상관 없음 
            set[idx].push_back(i++);
            cnt++;
        }
        ht[idx++].second = cnt-1;
    }
    int order = 1;
    int set_idx = n-1;
    /* 넣는 숫자가 untill보다 크면 out! */
    while(order <= untill)
    {
        // 패턴 (1) 왼쪽 아래 방향 : head 1개씩 처리
        for(int i=0;i<set.size();i++)
        {
            int head = ht[i].first;
            int tail = ht[i].second;
            if(head <= tail) {
                set[i][head] = order++;
                ht[i].first++;
            }
        }
        // 패턴 (2) 왼쪽에서 오른쪽 방향 : 묶음 전체 처리
        for(int i=ht[set_idx].first;i<set[set_idx].size();i++)
        {
            int head = ht[set_idx].first;
            int tail = ht[set_idx].second;
            // head <= tail
            if(head <= tail){
              set[set_idx][i] = order++;
              ht[set_idx].first++;
            } 
        }
        set_idx--;
        // 패턴 (3) 오른쪽 아래에서 위 방향 : tail 1개씩 처리
        for(int i=set_idx;i>=0;i--)
        {
            int head = ht[i].first;
            int tail = ht[i].second;
            if(head <= tail) {
                set[i][tail] = order++;
                ht[i].second--;
            }
        }
    }
    /* answer에 답 쌓기 */
    for(int i=0;i<set.size();i++)
    {
        for(int j=0;j<set[i].size();j++)
        {
            answer.push_back(set[i][j]);
        }
    }
    return answer;
}

1) 각 수들을 묶음별로 2차원 배열 형태의 vector에 저장함
2) 각 층마다 head / tail 이라는 변수를 두고 증 / 감 해가면서 특징을 찾아서 해결함

---

[ 최적 코드 ] - 특징을 찾아서 해결

#include <string>
#include <vector>
using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    vector<vector<int>> arr(n);
    int order=1;
    int x=0, y=-1;
    int resize=1;
    int state = 0;
    for(int i=0;i<arr.size();i++) arr[i].resize(resize++);
    /* 3개의 패턴들 에서 일어나는 연산 수가 n -> n-1 ... 1 까지 규칙이 있음 */
    for(int i=n;i>0;i--)
    {
        /* 패턴 (1) : 왼쪽 아래로 이동 */
        if(state == 0){
            for(int j=0;j<i;j++) arr[++y][x] = order++;
            state=1;
        }else if(state == 1){
        /* 패턴 (2) : 오른쪽으로 이동 */
            for(int j=0;j<i;j++) arr[y][++x] = order++;
            state=2;
        }else if(state == 2){
        /* 패턴 (3) : 오른쪽 위로 이동 */
            for(int j=0;j<i;j++) arr[--y][--x] = order++;
            state=0;
        }
    }
    /* answer에 답 쌓기 */
    for(int i=0;i<arr.size();i++)
        for(int j=0;j<arr[i].size();j++)
            answer.push_back(arr[i][j]);
    return answer;
}

• key point !
  1) 3개의 패턴을 state라는 변수로 관리
  2) 각 패턴 내부에서 일어나는 연산 수에 패턴이 있다
      (n -> n-1 -> n-2 ... -> 1)
  3) x와 y좌표를 이용해서 패턴을 수행함