2025.4.1 알고리즘 코드카타

알고리즘 코드카타 - 108. 삼각 달팽이

문제 링크

풀이 참고 : https://yabmoons.tistory.com/575

문제 설명

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• n은 1 이상 1,000 이하입니다.

---

입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2
문제 예시와 같습니다.

입출력 예 #3
문제 예시와 같습니다.

---

풀이 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    // n * n 크기의 2차원 배열
    vector<vector<int>> snail(n+1,vector<int>(n+1,0));
    // 배열 좌표 진행방향
    int dx[] = {1, 0, -1};
    int dy[] = {0, 1, -1};
    
    int movecount = 0, dir = 0;  // 이동 횟수, 이동방향 인덱스
    int tomove = n;     // 이동해야 할 횟수
    int i = 1, j = 1, value = 1;// x좌표, y좌표, 배열에 들어갈 값
    
    while(tomove > 0)
    {
        // 이차원 배열에 값 입력 후 이동 횟수 증가
        snail[i][j] = value++;
        movecount++;
        
        // 이동해야 할 횟수만큼 이동했으면 방향 전환
        if(movecount == tomove)
        {
            dir = (dir+1) % 3;
            movecount = 0;
            tomove--;
        }
        
        i += dx[dir];
        j += dy[dir];
    }
    
    // 전체 이동 완료시 0 제외한 값 일차원배열에 옮기기
    for (i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if (snail[i][j] != 0)
            {
                answer.push_back(snail[i][j]);
            }
        }
    }
    return answer;
}

풀이 설명

• 변의 길이가 n+1인 정사각형 이차원배열을 선언 (좌표를 (1,1)부터 시작하기 위함)

• 채우기가 끝난 후 이차원배열을 전부 순회해서 값이 0이 아닌 원소만 정답 배열 answer에 추가한다.

---

방향 전환이 언제 일어나는지, 방향 전환을 어떻게 하는 지를 파악하는 것이 핵심인 문제였다. 너무 어려워서 다른 사람의 풀이를 봤는데, 너무 복잡해서 그나마 간단하고 이해하기 쉬운 풀이를 참고했다.
그래도 이렇게 로직을 보고 나니 다른 풀이도 조금씩 이해가 되기 시작한다는 게 다행이다.