[Programmers] 삼각 달팽이

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

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

규칙을 보면 n * (n + 1) / 2 즉, 1부터 n까지 더했을 때의 값이 삼각 달팽이의 마지막 숫자입니다.

따라서, 마지막 숫자를 입력할 때까지 회전을 시킨 뒤 answer 벡터에 순서대로 숫자를 넣어주면 되는 문제였습니다.

 

	#include <string>
	#include <vector>
	using namespace std;
	const int MAX = 1000;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[3] = { { 1, 0 }, {0, 1}, {-1, -1} };
	int triangle[MAX][MAX];
	vector<int> solution(int n) {
	int y = -1, x = 0;
	int idx = 1;
	int dir = 0;
	while (1)
	{
	if (idx == n * (n + 1) / 2 + 1)
	{
	break;
	}
	int nextY = y + moveDir[dir].y;
	int nextX = x + moveDir[dir].x;
	if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= n
	|| triangle[nextY][nextX])
	{
	dir = (dir + 1) % 3;
	continue;
	}
	triangle[nextY][nextX] = idx++;
	y = nextY;
	x = nextX;
	}
	vector<int> answers;
	for (int i = 0; i < n;i++)
	{
	for (int j = 0; j < n; j++)
	{
	if (triangle[i][j])
	{
	answers.push_back(triangle[i][j]);
	}
	}
	}
	return answers;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

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