Programmers 68645 삼각 달팽이

09 Mar 2021 in Algorithm

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

나의 풀이

숫자를 채울 때 반시계 방향으로 채우기 때문에 숫자를 채우는 방향은 ↙, → ,↖ 3가지 방향이 반복된다.
각 방향마다 다음 숫자의 인덱스를 결정하는 규칙이 있다.
먼저 ↙ 방향은 현재 인덱스에서 높이 h만큼 더하면 다음 인덱스가 된다. (높이는 위에서부터 1이며, ↙ 방향이면 h를 1씩 증가한다.)
→ 방향은 현재 인덱스에서 1을 더한값이 다음 인덱스가 된다.
↖ 방향은 현재 인덱스에서 높이 h만큼 빼면 다음 인덱스가 된다. (↖ 방향이면 h를 1씩 감소한다.)
방향은 ↙, → ,↖ 순서로 바뀌며, 방향이 바뀌면 방향을 유지하는 길이 k를 1씩 줄인다.

예를 들어 n=4일 때를 생각하면

1. 숫자 1은 0번 인덱스에 넣는다. 초기 방향은 ↙이기 때문에 다음 인덱스는 현재 높이 1에 현재 인덱스 0을 더해 1이 되며, ↙방향이기 때문에 높이를 1증가
2. 마찬가지로 인덱스 1에 다음숫자 2를 넣고 next index = h + index = 2+1 = 3, h=h+1
3. 인덱스 3에 다음숫자 3을 넣고 next index = h + index = 3 + 3 = 6 , h=h+1
4. 인덱스 6에 숫자 4를 넣고 → 방향으로 바뀌기 때문에 next index = index + 1 = 7
5. 인덱스 7에 숫자 5 넣고 next index = index + 1 = 8
6. 인덱스 8에 숫자 6 넣고 next index = index + 1 = 9
7. 인덱스 9에 숫자 7 넣고 방향이 ↖로 바뀌어 next index = index-h = 9-4 = 5, h=h-1
8. 인덱스 5에 숫자 8 넣고 next index = 5 - 3 = 2, h=h-1
9. 인덱스 2에 숫자 9 넣고 방향이 다시 ↙로 바뀌고 next index = h + index = 2 + 2 = 4, h=h+1
10. 인덱스 4에 숫자 10 넣고 모든 숫자를 다 넣어 종료

풀이 코드 : 68645 삼각 달팽이

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

vector<int> solution(int n) {
    int size = 0;
    for(int i=1;i<=n;i++){
        size += i;        
    }
    vector<int> answer;
    answer.resize(size);
    char DRU[] = {'D', 'R', 'U'};
    int dru_idx = 0;
    int idx = 0;
    int j =1;
    int k = n;
    int h = 1;
    for(int c = 1;c<=size;c++,j++){
        answer[idx] = c;
        if(DRU[dru_idx] == 'D'){
            if(j < k){
                idx = h + idx;
                h++;
            }
            else{
                k--;
                j = 0;
                idx++;
                dru_idx++;
            }
        }
        else if(DRU[dru_idx]  == 'R'){
            if(j<k){
                idx++;
            }
            else{
                k--;
                j=0;
                idx = idx - h;
                dru_idx++;
                h--;
            }
        }
        else if(DRU[dru_idx == 'U']){
            if(j<k){
                idx = idx - h;
                h--;
            }
            else{
                k--;
                j=0;
                dru_idx=0;
                idx = h + idx;
                h++;
            }
        }
    }
    return answer;
}

int main(){
    vector<int> arr;
    int n;
    cin>>n;
    arr = solution(n);
    for(int i=0;i<arr.size();i++)
        cout<<arr[i]<<" ";
}

채점결과