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

문제 설명

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

제한사항

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

 

입출력 예

 

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

 

풀이

이 문제는 규칙을 찾아야 하는데 어떻게 푸냐에 따라서 많은 방법이 있을 것 같다.

반시계 방향 순서대로 왼쪽 -> 아래 -> 오른쪽 순서로 3등분으로 나눠서 풀었다.

 

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

// 현재 인덱스가 몇 레벨에 위치하는지 반환하는 함수
int findLevel(int idx){
    int level;
    
    for(int i=0; i<1000; i++){
        int start = i*(i+1)/2;
        int end = i*(i+1)/2 + i;
        
        if(start<=idx && end>=idx){
            level = i;
            break;
        }
    }
    
    return level;
}

vector<int> solution(int n) {
    int size = n*(n+1)/2;
    vector<int> answer(size);
    vector<bool> visit(size);
    
    int num = 0;
    int idx = 0;
    
    while(num != size){
    
    	// idx는 현재 루트 위치 (각 소용돌이의 시작점)
    	// cnt는 다음,이전 레벨로 가기위한 증감 인덱스
        int cnt = findLevel(idx);
        
        // 반시계 방향의 왼쪽
        while(num != size){
            answer[idx] = ++num;
            visit[idx] = 1;
            ++cnt;
            
            if(idx + cnt >= size) break;
            if(visit[idx + cnt]) break;
            
            idx += cnt;
        }
        
        // 반시계 방향의 아래쪽
        ++idx;
        while(num != size){
            answer[idx] = ++num;
            visit[idx] = 1;
            
            if(idx + 1 >= size) break;
            if(visit[idx + 1]) break;
            
            ++idx;
        }
        
        // 반시계 방향의 오른쪽
        idx -= cnt;
        while(num != size){
            answer[idx] = ++num;
            visit[idx] = 1;
            --cnt;
            
            if(visit[idx - cnt]) break;
            idx -= cnt;
        }
        
        // 다음 소용돌이의 루트로 이동
        idx += findLevel(idx) + 1;
    }

    return answer;
}