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

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

프로그래머스

문제 유형 : 구현 / 배열

문제 난이도 : Level 2

 

문제 설명

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

풀이

달팽이 배열의 모양을 직각삼각형으로 생각한다.

다음의 단계를 거친다:

 1. i의 인덱스를 높이면서 값을 배열에 담기

 2. j의 인덱스를 높이면서 값을 배열에 담기

 3. i와 j의 인덱스를 낮추면서 값을 배열에 담기

단, 각 과정 사이에 조정 작업이 필요하다.

예를 들면, 1번과정을 거치고, 4번 자리에 있는 인덱스를 5번으로 옮겨서 2번 과정을 시작한다던가.

2번과정을 거치고, 7번 자리에 있는 인덱스를 8번으로 옮긴다던가.

3번과정을 거리고, 9번 자리에 있는 인덱스를 10번으로 옮기는 식의 조정 작업을 해주면 된다.

 

그리고 배열을 순차적으로 돌아주면서 값이 있는 배열만 1차원배열에 담아주면 된다.

 

코드

 

C++

#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<vector<int>> snail(n, vector<int>(n, 0));
    
    int max_num = n * (n + 1) / 2;
    int num = 1;
    int row = 0, col = 0;
    
    while (num <= max_num) {
        while (row < n && snail[row][col] == 0) {
            snail[row++][col] = num++;
        }
        row--;
        col++;
        
        while (col < n && snail[row][col] == 0) {
            snail[row][col++] = num++;
        }
        col -= 2;
        row--;
        
        while (row >= 0 && col >= 0 && snail[row][col] == 0) {
            snail[row--][col--] = num++;
        }
        row += 2;
        col++;
    }
    
    vector<int> answer;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            answer.push_back(snail[i][j]);
        }
    }
    
    return answer;
}

 

Python3

def solution(n):
    snail = [[0] * n for _ in range(n) ]
    num = 1 
    row = 0 
    col = 0
    maxNum = n * (n + 1) // 2
    
    while num <= maxNum:
        while row < n and snail[row][col] == 0:
            snail[row][col] = num
            row += 1
            num += 1
        row -= 1
        col += 1
        
        while col < n and snail[row][col] == 0:
            snail[row][col] = num
            col += 1
            num += 1
        col -= 2
        row -= 1
        
        while row >= 0 and col >= 0 and snail[row][col] == 0:
            snail[row][col] = num
            col -= 1
            row -= 1
            num += 1
        col += 1
        row += 2
    
    answer = []
    for i in range(n):
        for j in range(n):
            if snail[i][j] != 0:
                answer.append(snail[i][j])
    return answer