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

 이 문제는 규칙성을 찾아서 구현하는 문제이다. 일단 n의 최댓값이 1,000이고, 마지막 숫자는 1000 * 1001 / 2 = 500,500이 될 것이므로 O(n)의 알고리즘으로 충분히 가능하다.

 

 

 내가 활용한 규칙성 첫번째는 (n - 1) / 3 + 1 이 총 삼각형의 개수라는 것이다. 각각 n이 1, 4, 7, 10일 때 삼각형 1, 2, 3, 4개이다. 두번째는 각 삼각형의 시작 위치가 0,0부터 시작해서 y좌표는 2씩, x좌표는 1씩 증가한다는 것이다. 이 두가지 규칙을 활용해서 fill 함수를 만들었고, dist는 몇번째 삼각형인지를 나타낸다. fill 함수는 해당 삼각형의 외곽에 대한 숫자를 집어넣는 함수로 생각하여 구현했다. endY와 endX를 구할때 실수만 없다면 구현도 쉽고, 문제도 쉽게 풀린다.

 

 

 

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

using namespace std;

int number;

void fill(vector<vector<int>>& triangle, int n, int dist, int startY, int startX) {
    int endY = n - dist - 1;
    int endX = triangle[endY].size() - 1 - dist;
    
    // left
    for (int y = startY; y <= endY; y++) {
        triangle[y][dist] = number;
        number++;
    }
    
    // down
    for (int x = dist + 1; x <= endX; x++) {
        triangle[endY][x] = number;
        number++;
    }
    
    // right
    for (int y = endY - 1; y >= startY + 1; y--) {
        int last = triangle[y].size() - dist - 1;
        triangle[y][last] = number;
        number++;
    }
}

vector<int> solution(int n) {
    vector<int> answer;
    
    vector<vector<int>> triangle(n);
    
    for (int i = 0; i < n; i++) {
        triangle[i] = vector<int>(i + 1, 0);
    }
    
    int cnt = (n - 1) / 3;
    
    int startY = 0, startX = 0;
    
    number = 1;
    
    for (int c = 0; c <= cnt; c++) {
        fill(triangle, n, c, startY, startX);
        startY += 2;
        startX += 1;
    }
    
    for (vector<int>& t : triangle) {
        for (int num : t) {
            answer.push_back(num);
        }
    }
    
    return answer;
}