[알고리즘] Level 3) 삼각달팽이 - C++

문제 설명

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

 

 

제한사항

n은 1 이상 1,000 이하입니다.

 

입출력 예

4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

 

접근방법

- 달팽이를 채우는 방법을 그대로 생각해보자 !

 

state 가 0 일때 : 아래로 이동

state 가 1 일때 : 오른쪽으로 이동

state 가 2 일때 : 왼쪽위로 이동

 

이 이동을 n 만큼 반복한다. ex) n=5 인경우 아래 → 위 → 왼쪽위 → 아래 → 위

 

코드

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

vector<int> solution(int n) {
	vector<int> answer;
	int arr[1000][1000] = { 0 };
	int state = 0, cnt = 0;
	int num = 1;
	int x = 0, y = 0;
	int temp = n;
	while (cnt < n) {
		switch (state) {
		case 0:
			for (int i = 0; i < temp; i++, num++) {
				arr[y++][x] = num;
			}
			y--;
			x++;
			state = 1;
			break;
		case 1:
			for (int i = 0; i < temp; i++, num++) {
				arr[y][x++] = num;
			}
			x = x - 2;
			y--;
			state = 2;
			break;
		case 2:
			for (int i = 0; i < temp; i++, num++) {
				arr[y--][x--] = num;
			}
			y = y + 2;
			x++;
			state = 0;
			break;
		}

		cnt++;
		temp--;
	}
	int k = 1;
	for (int a = 0; a < n; a++) {
		for (int b = 0; b < k; b++) {
			answer.push_back(arr[a][b]);
		}
		k++;
	}
	return answer;
}

 

주의할 점 

for(int i =0 ; i< 5 ; i++) 인 경우 , for 문을 다 돌면 i=5 라는 점 !

따라서 state 가 바뀔 때 다음 시작 인덱스를 제대로 맞춰줘야 한다.