프로그래머스 - 삼각 달팽이 (C++)

 

---

 

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

프로그래머스

 

 이번 문제는 정수 n이 주어졌을 때, 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 찾는 문제이다. 단순한 구현 문제이기에 삼각형의 가장 윗 꼭짓점에서부터 실제로 번호를 매기면 된다. 이를 위해 vector<vector<int>> triangle이라는 벡터를 이용하였다. triangle은 길이가 n인 vector이다. 그리고 triangle[k]는 길이가 k + 1인 vector이다.(n일 경우, triangle은 0부터 n-1까지이다.) 즉, n의 값이 4일 경우, 아래같은 모습을 가진다.

위의 이미지는 모든 값이 0으로 초기화된 triangle을 나타낸 것이다. 이제 번호를 매기는 과정을 생각해볼 것이다. 우선, 방향이다. 번호를 매기기 위한 진행 방향은 아래, 오른쪽, 위로 총 3가지이며 방향의 순서는 아래 -> 오른쪽 -> 위 -> 아래 -> 오른쪽 -> 위 -> 아래 -> ... 이다.. 여기서 위로 갈 때를 주의해야 한다. (r, c)에서 아래는 (r + 1, c), 오른쪽은 (r, c + 1)이다. 하지만 위는 (r - 1, c - 1)로 r, c 둘 다 건드려야 한다. ((r, c)는 triangle[r][c]를 의미한다.)

진행 방향

왜냐하면 위의 이미지에서도 알 수 있듯이 아래, 오른쪽은 단순히 수직, 수평으로 움직이지만 위는 대각선 방향으로 움직이기 때문이다. 마지막으로 범위이다. 만약 다음 방향이 삼각형의 범위를 벗어날 경우, 방향을 바꿔서 진행해야 한다. 삼각형의 범위를 검사하는 코드는 다음과 같다.

 

bool IsIn(int r, int c)
{
	if (0 > r || r >= N)
		return false;

	return 0 <= c && c <= r;
}

(r, c)를 입력 받는다. triangle은 0부터 n - 1까지 존재하므로 r이 이 범위를 벗어날 경우 false를 반환한다. 그리고 c(좌우 길이)의 값은 0 이상 r 이하이므로 0 <= c && c <= r로 나타낼 수 있다. 다음은 이것들을 고려한 코드이다.

 

#include <string>
#include <vector>
#define DOWN 0
#define RIGHT 1
#define UP 2
using namespace std;

int N;
int lastNum = 0;
vector<vector<int>> triangle; 

int nr[3] = { 1, 0, -1 };
int nc[3] = { 0, 1, -1 };

bool IsIn(int r, int c)
{
	if (0 > r || r >= N)
		return false;

	return 0 <= c && c <= r;
}

int ChangeDirection(int dir)
{
    if (dir == UP)
        return DOWN;
    else
        return dir + 1;
}

void Check(int r, int c, int num, int dir)
{
	if (num > lastNum)
        return;

    triangle[r][c] = num;
    
    int nxtR = r + nr[dir];
    int nxtC = c + nc[dir];

	if (IsIn(nxtR, nxtC))
	{
		if (triangle[nxtR][nxtC] > 0)
		{
			dir = ChangeDirection(dir);

			nxtR = r + nr[dir];
			nxtC = c + nc[dir];
		}
	}
	else
	{
		dir = ChangeDirection(dir);

		nxtR = r + nr[dir];
		nxtC = c + nc[dir];
	}

	Check(nxtR, nxtC, num + 1, dir);
}

vector<int> solution(int n) {
    vector<int> answer;
    
    N = n;
    
    for (int h = 1; h <= n; ++h)
    {
        vector<int> line;
        
        for (int k = 0; k < h; ++k)
            line.push_back(0);
        
        triangle.push_back(line);
    }
    
    for (int k = 1; k <= n; ++k)
        lastNum += k;
    
	Check(0, 0, 1, DOWN);

    for (int r = 0; r < triangle.size(); ++r)
    {
        for (int c = 0; c < triangle[r].size(); ++c)
            answer.push_back(triangle[r][c]);
	}
    
    
    return answer;
}

번호 매기기는 현재 숫자가 n의 값에 따른 마지막 숫자보다 클 경우 중단한다.