C++ / 프로그래머스 / 삼각 달팽이

문제

 

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

프로그래머스

 

 

문제풀이

해당 그림을 2차원 벡터로 표현할 것이다.

벽돌들을 맨 왼쪽으로 모두 당긴 모양을 생각하면 된다.

 

맨 위 맨 왼쪽 벽돌부터 시작하여 숫자는 아래로, 오른쪽으로, 왼쪽 대각선으로 이동하며 커진다.

 

    for (int y = 0; y < N; ++y) {
        board[y] = vector<int>(y + 1, 0);
        max_size += y + 1;
    }

맨 위줄은 y=0, 개수는 1개이다.

그다음 줄은 y=1, 개수는 2개이다. 이런 식으로 y에 맞춰 board의 사이즈를 조절한다.

 

bool isBreak(int y, int x) {
    if (y < 0 || x < 0) return true;
    else if (y >= board.size()) return true;
    else if (x >= board[y].size()) return true;
    else if (board[y][x] != 0) return true;
    else if (num > max_size) return true;
    else return false;
}

해당 좌표가 없는 좌표이거나, 이미 채워졌거나, 모든 블록을 채웠는지를 검사하는 함수이다.

true를 return 하면 멈춰야 하고 false를 return 하면 계속 진행하라는 의미이다.

 

    while (1) {
        if (num >= max_size) break;
        while (1) {
            if (isBreak(y, x) == false) {
                board[y][x] = ++num;
                ++y;
            }
            else {
                --y;
                ++x;
                break;
            }
        }
        while (1) {
            if (isBreak(y, x) == false) {
                board[y][x] = ++num;
                ++x;
            }
            else {
                x -= 2;
                --y;
                break;
            }
        }
        while (1) {
            if (isBreak(y, x) == false) {
                board[y][x] = ++num;
                --y;
                --x;
            }
            else {
                y += 2;
                x += 1;
                break;
            }
        }
    }

코드가 아래로 길긴 한데 별 내용은 없다.

먼저 아래쪽으로, y가 증가하면서 숫자를 넣을 수 있는 블록이 있는지 확인을 한다.

없다면 오른쪽으로, x가 증가하는 방향으로 가야 하므로 해당 좌표로 이동한다.

 

그다음은 오른쪽으로 x를 증가시키면서 이동한다.

만약 더 갈 수 없다면 왼쪽 위 대각선으로 가야 하므로 해당 좌표로 이동한다.

 

그다음은 왼쪽 위 대각선으로 y, x를 감소시키면서 이동한다.

만약 더 갈 수 없다면 아래쪽으로 가야 하므로 해당 좌표로 이동하고 while문을 계속 반복한다.

 

만약 모든 블록을 채웠다면 반복문을 종료한다.

 

 

 

코드

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

vector<vector<int>>board;
int num, max_size;
bool isBreak(int y, int x) {
    if (y < 0 || x < 0) return true;
    else if (y >= board.size()) return true;
    else if (x >= board[y].size()) return true;
    else if (board[y][x] != 0) return true;
    else if (num > max_size) return true;
    else return false;
}

vector<int> solution(int N) {
    vector<int> answer;

    board = vector<vector<int>>(N);

    for (int y = 0; y < N; ++y) {
        board[y] = vector<int>(y + 1, 0);
        max_size += y + 1;
    }

    int y(0), x(0);

    while (1) {
        if (num >= max_size) break;
        while (1) {
            if (isBreak(y, x) == false) {
                board[y][x] = ++num;
                ++y;
            }
            else {
                --y;
                ++x;
                break;
            }
        }
        while (1) {
            if (isBreak(y, x) == false) {
                board[y][x] = ++num;
                ++x;
            }
            else {
                x -= 2;
                --y;
                break;
            }
        }
        while (1) {
            if (isBreak(y, x) == false) {
                board[y][x] = ++num;
                --y;
                --x;
            }
            else {
                y += 2;
                x += 1;
                break;
            }
        }
    }

    for (int y = 0; y < N; ++y) {
        for (int x = 0; x <= y; ++x) {
            answer.push_back(board[y][x]);
        }
    }

    return answer;
}