프로그래머스 - 삼각 달팽이

문제 링크입니다 : programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

 

 

 

각 껍질을 별로 채워나간다고 생각하면 쉽게 해결할 수 있다.

그리고 껍질의 길이(변의 길이)가 줄어드는 규칙이 3씩 감소하는 등차수열의 규칙을 따르고 있다.

사실 문제에 대단한 규칙이 있다기 보다는 그냥 얼마나 주어진 조건에서 규칙을 잘 발견할 수 있는지를 측정하는 문제라고 생각한다.

 

 

(주의 : 이 해설에서 한 변의 길이는 위의 그림처럼 세 방향으로 감쌀 수 있는 각 길이를 의미함. 오해의 소지가 없길 바랍니다.)

 

n = 5인 경우에 바깥 껍질 한 변이 4이고 내부 껍질이 1이다. 그 다음은 껍질 길이가 -2가 되서 채울 필요 없이 끝나게 된다.

 

n = 6인 경우에는 바깥 껍질 한 변이 5이고 내부 껍질이 2이다. 그 다음은 껍질 길이가 -1가 되서 채울 필요 없이 끝나게 된다.

 

n = 4인 경우가 조금 특별하다. 바깥의 껍질을 다 채우더라도 내부에 공간 딱 하나만 남는 특별한 경우가 있다. 이런 경우에는 바깥 껍질의 길이가 3일 때 그렇다. 이럴 때는 길이가 3인 껍질을 다 채우고 내부에 마지막 남은 한칸을 채우고 끝내면 된다.

 

 

 

 

위 과정에 대한 수학적인 규칙은 나도 잘 모르겠다. 하지만 귀납적 추론 능력 또한 굉장히 중요한 요소이다. 이런 문제들이 수학적인 규칙을 잘 모르더라도 충분히 유추할 수 있는지 능력을 묻는 문제라고 할 수 있다.

 

 

(혹시 다른 문제에 대한 해설이 필요하거나 본 문제에 대한 추가 해설이 필요하다면 댓글을 남겨주세요. 추가 해설 작성후 댓글로 알림을 드리겠습니다.)

 

 

 

 

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

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    
    vector<vector<int>> board(n, vector<int>(n, 0));
    
    // cnt : 각 칸에 채울 숫자 값
    // y,x : 현재 채우고 있는 위치의 칸의 좌표
    int cnt = 1;
    int y = 0, x = 0;
    
    for(int len = n - 1; len >= 0; len -= 3) {
        
        // 마지막 중심에 하나만 남았을 때
        if(len == 0) {
            board[y][x] = cnt;
            break;
        }
        
        // 위에서 왼쪽 아래로
        // 이동하며 숫자 채우기
        for(int i = 0; i < len; i++) {
            board[y][x] = cnt++;
            y++;
        }
        
        // 혹시 다 채웠으면 끝내기
        if(board[y][x]) {
            break;
        }
        
        // 왼쪽 아래에서 오른쪽 아래로
        // 이동하며 숫자 채우기
        for(int i = 0; i < len; i++) {
            board[y][x] = cnt++;
            x++;
        }
        
        // 혹시 다 채웠으면 끝내기
        if(board[y][x]) {
            break;
        }

        // 오른쪽 아래에서 위로
        // 이동하며 숫자 채우기
        for(int i = 0; i < len; i++) {
            board[y][x] = cnt++;
            x--;
            y--;
        }
        
        // 내부 껍질 시작점으로 좌표 이동
        y += 2;
        x++;

    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(board[i][j]) answer.push_back(board[i][j]);
        }
    }
    
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~