[프로그래머스][월간 코드 챌린지 시즌 1][C++] 삼각 달팽이

문제

프로그래머스 월간 코드 챌린지 시즌 1 - 삼각 달팽이 (Level 2)

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

 

---

문제 풀이

접근 방식

이 문제는 프로그래머스 월간 코드 챌린지 시즌 1 2번 문제로,

아래의 그림과 같이 삼각형의 맨 위 꼭짓점부터 반시계 방향으로 숫자를 채워서,

첫 행부터 마지막 행까지 합친 새로운 배열을 구하는 문제이다.

 

 

우선 n×n 크기의 result 벡터를 만들어 모든 값을 -1로 할당해주었다.

이후 ↓ - → - ↖방향으로 이동하며 숫자를 채워주었다.

숫자를 채우는 과정은 방향을 바꿔야 하는 조건을 고려하여 다음과 같이 구현해주었다.

while (1) {
	for (int i = 0; i < 3; i++) {
		while (1) {
			if (num > end) break;
			x += dir[i][0], y += dir[i][1];
			if (x >= n || y >= n || result[x][y] != -1) {
				x -= dir[i][0], y -= dir[i][1];
				break;
			}
			result[x][y] = num++;
		}
		if (num > end) break;
	}
	if (num > end) break;
}

 

이후, 삼각형 모양으로 각 행을 탐색하며 answer 벡터에 순서대로 넣어주어 답을 리턴하였다.

 

---

풀이 코드 - C++

#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<vector<int>> result(n, vector<int>(n, -1));
    int end = 0;
    for (int i = 1; i <= n; i++) end += i;
    int dir[3][2] = { {1,0},{0,1},{-1,-1} };
    int x = 0, y = 0, cnt = 1, num = 2;
    result[x][y] = 1;
    while (1) {
        for (int i = 0; i < 3; i++) {
            while (1) {
                if (num > end) break;
                x += dir[i][0], y += dir[i][1];
                if (x >= n || y >= n || result[x][y] != -1) {
                    x -= dir[i][0], y -= dir[i][1];
                    break;
                }
                result[x][y] = num++;
            }
            if (num > end) break;
        }
        if (num > end) break;
    }

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

실행 결과

실행 결과 : 100.0