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

[문제]

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

 

[풀이]

처음에는 규칙성을 찾고 인덱스를 하나씩 선형 탐색하면서 push_back을 하려다가(좀 오래 고민함), 이건 아닌거 같아서 다른 방법을 생각했다. 먼저 2차원 배열을 준비한 다음 아래, 오른쪽, 위-왼쪽(대각선) 방향으로 채워나가는 방식이다.

 

1. 2차원 테이블 생성

2. 각 인덱스 값에 접근할 요소들 선언

3. 탐색 시작, max값이 되면 종료한다.

  3-1. 방문한 테이블 좌표값에 대해 num을 입력하고, 1 증가시켜준다.

  3-2. 현재 방향에 대해 먼저 y를 1 증가, x는 그대로 탐색 시도, 이 값이 경계를 벗어났는지 확인함

    3-2-1. 경계를 벗어난 경우(사이즈를 벗어나거나 값이 채워진 인덱스인 경우), 방향 전환을 시도

    3-2-2. 시도 방식은 dir(방향 인덱스)를 재설정하고, 해당 방향 인덱스를 기준으로 탐색할 좌표값을 덮어써줌

  3-3. 경계가 벗어나지 않았으면 좌표를 재설정

4. 3의 방식을 반복하여 값을 채워넣은 뒤, 2차원 배열을 answer에 담고 return

 

규칙성을 찾지 않고 그냥 채워넣었으면 금방 풀었을 것이다(아쉬운 부분). 아래는 구현 코드이다.

#include <vector>

using namespace std;

int dy[3] = { 1, 0, -1 };
int dx[3] = { 0, 1, -1 };

vector<int> solution(int n)
{
    // 삼각형 구조를 표현할 2차원 벡터
    vector<vector<int>> triangle(n, vector<int>(n, 0));

    // 방향 벡터: 아래, 오른쪽, 왼쪽 위 대각선
    int dy[3] = { 1, 0, -1 };
    int dx[3] = { 0, 1, -1 };

    int y = 0;
    int x = 0;
    int num = 1;
    int dir = 0; // 방향 인덱스
    int maxNum = n * (n + 1) / 2;

    while (num <= maxNum) 
    {
        triangle[y][x] = num++;

        int ny = y + dy[dir];
        int nx = x + dx[dir];

        // 경계를 벗어나거나 이미 숫자가 채워져 있으면 방향 전환
        if (ny >= n || nx >= n || ny < 0 || nx < 0 || triangle[ny][nx] != 0) 
        {
            dir = (dir + 1) % 3;
            ny = y + dy[dir];
            nx = x + dx[dir];
        }

        y = ny;
        x = nx;
    }

    // 결과를 1차원 벡터로 변환
    vector<int> answer;
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j <= i; j++) 
        {
            answer.push_back(triangle[i][j]);
        }
    }

    return answer;
}