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

이얀조·2023년 10월 6일

🎀프로그래머스

목록 보기

21/21

삼각 달팽이 68645

🥐 문제 설명

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

🥨 제한사항

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

🍯 풀이

딱히 정해진 알고리즘이 있는 것이 아니라, 규칙 을 찾아야 한다.!

위의 예시는 N = 7 인 경우를 나타낸다.

현재 빨간색으로 테두리를 친 경우가 규칙을 1회 돌았을 때 탐색되는 구간이다.
2회 차 돌았을 경우 한줄 더 "안" 으로 들어간 [19, 20, 21, 22, 23, 24, 25, 26, 27] 이 될 것이다.

정확한 규칙은 아니지만, 내가 발견한 규칙 위주로 풀이를 해보면 다음과 같다.

1. 열은 그대로, 행만 "증가"

화살표를 그려둔 것 처럼 탐색을 할 경우 각 행 의 0 번째 인덱스만 탐색하는 것을 알 수 있다.
만약 2회 차에 이 경우를 반복한다면 [19, 20, 21, 22] 와 같이 현재의 행 의1 번째 인덱스만 탐색할 것이다.

나는 행의 경우에는 현재의 행, 즉 1회차의 경우 (0, 0) 이므로 0 에서 시작하여 N - turn 까지 탐색하게 된다고 보았다.
(이때 IDX 로 접근해야하므로 N - turn - 1 을 잊지말자 !)

자연스럽게 열의 경우에는 현재의 turn, 즉1회차의 경우 1 이라고 생각했다.
(그러나 이때 IDX 를 좀 더 편하게 두기 위해 turn - 1 보다는 turn 을 0 으로 초기화 하여 이 반복문이 끝나고 1을 더해주었다.)

2. 열만 "증가"

1번과 비슷하게 풀이할 수 있다.
2번의 경우 열만 증가해 주면 된다. 동일하게 행의 경우 현재의 행 을 유지하고, 열만 증가시키면 된다.

이때 N - turn 인 이유는 회차가 거듭될 수록 양 끝이 이미 탐색되었기 때문에 turn 만큼 들어가지기 때문이다 ㅎ ㅎ

이후 열의 경우 현재의 열 에서 N - turn 만큼 증가 시킨다. (IDX 접근을 위해 동일하게 1을 빼준다.)

헷갈릴 수 있어서 2회 의 경우에도 그려봤다!
2회 차의 1번 경우가 끝나면 22 의 위치에 행 이 위치할 것이다.
따라서 행은 유지하고, 열은 N - turn - 1(7 - 2 - 1 = 4) 번 인덱스까지 증가할 수 있다.

3. 행만 "감소"

가장 헷갈렸던 부분이다. .
열의 경우 2번의 경유가 끝난 위치에서 1만큼 빼준 14에서 시작한다.
(미리 열을 1만큼 빼줌!)

이후 계속 행을 감소시켜주면 된다.
그러나 이때, 열 의 IDX 를 신경써주어야 하는 부분이 있다.

각 행마다 열의 길이가 다르기 때문에, 그 열의 길이(k) - turn + 1 을 해 주어야 한다 . . . .

Q. 왜 +1 을 해주어야 하는가?
└ 이 부분 때문에 그렇게 시간을 잡아먹었다 !!!!
나는 계속해서 IDX 로 접근을 해서 k 가 IDX 기준으로 잡혀있는데, 따라서 이미 1을 빼준 상태이기 때문이다.
그냥 k를 쓰면 된다고 생각했었는데, 그러면 다음회차부터 안쪽으로 들어갈 수 없다 . .
-> 2회 차에 계속 1회에 접근한 곳만 탐색하게 되는 오류 발생

리마인드를 위해 풀이를 작성하고 있지만. . .
다른사람이 보기에 쉽게 풀이가 되었는지 알 수 없다 ㅠ __ ㅠ

🧝🏻‍♀️ 코드

[C++]

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

vector<int> solution(int n) {
    vector<int> answer;
    vector<vector<int>> triangle;
    
    if (n == 1) {
        answer.push_back(1);
        return answer;
    }
    
    // setting triangle
    for (int i = 1; i <= n; i++) {
        vector<int> tmp;
        for (int j = 0; j < i; j++) tmp.push_back(0);
        triangle.push_back(tmp);
    }
    
    int col = 0, row = 0;
    int num = 1;
    int turn = 0;
    while(true) {
        if (triangle[col][row] > 0) break;
        
        // 1
        for (int i = col; i < n - turn; i++) {
            if (triangle[i][turn] == 0) {
                triangle[i][turn] = num++;
                col = i; row = turn;
            }
            else break;
        }
        row += 1; turn += 1; 
        
        // 2
        for (int j = row; j <= n - turn; j++) {
            if (triangle[n - turn][j] == 0) {
                triangle[n - turn][j] = num++;
                col = n - turn; row = j;
            }
            else break;
        }
        col -=1;
        
        // 3
        for (int k = col; k >= turn; k--) {
            if (triangle[k][k - turn + 1] == 0) {
                triangle[k][k - turn + 1] = num++;
                col = k; row = k - turn + 1;
            }
            else break;
        }
                
        col += 1;
    }
    
    for (int i = 0; i < triangle.size(); i++) {
        for (int j = 0; j < triangle[i].size(); j++) answer.push_back(triangle[i][j]);
    }
    return answer;
}

🤷🏻‍♂️ 어려웠던 점

유독 구현 문제에 취약하다는 생각이 들었다.
- 문제에 주어진 조건에 따라 그대로 구현만 하면 되는데, 생각보다 시간이 많이 소요되었다.
규칙을 찾아가며 침착하게 구축할 수 있도록 많이 풀어봐야 할 것 같다.

이얀조

이얀조다!

이전 포스트

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