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

공부 스파이럴·2023년 11월 13일

프로그래머스

목록 보기

3/18

문제

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

※주의

해당 풀이는 더럽고 비효율적입니다.
그냥 배열 만들고 순서대로 읽읍시다.

아이디어1

패턴을 파악

n > 3인 삼각형들을 봅시다.
변의 숫자들을 제거해보면 내부 구조는 3단계 전의 삼각형에 숫자만 바뀐 모양입니다.
예시) n = 5
1
2 12
3 13 11
4 14 15 10
5 6  7  8  9
->
13
14 15
->
n = 2인
1
2 3
에 12를 더한 모양

아이디어2

배열 채우기

n-3단계 삼각형에 (n-1) * 3만큼 숫자를 더합니다.
이제 좌우에 1개, 2개, 3개만큼 띄어가며 채워줍니다.
맨 위 3개, 맨 아래줄을 마지막에 채워줍니다.

중간 삽입이 많아서 list로 했습니다.

시작

    if (n == 1)
        return {1};
    if (n == 2)
        return {1, 2, 3};
    if (n == 3)
        return {1, 2, 6, 3, 4, 5};
    
    int remain = n % 3;
    
    list<int> arr;
    
    switch(remain)
    {
        case 0:
            arr = {1, 2, 6, 3, 4, 5};
            break;
        case 1:
            arr = {1};
            break;
        case 2:
            arr = {1, 2, 3};
            break;
    }

1, 2, 3일 땐 그냥 return
초기 배열 입력

배열 구하기

void Get_Array(int n, list<int>& arr)
{
    int remain = n % 3;
    if (remain == 0)
        remain = 3;
    remain += 2;
    
    for (int i = remain; i < n; i += 3)
    {
        int left = 2;
        int right = i * 3;
        for (auto& num : arr)
            num += right;
        
        left++;
        right--;
        
        int iterNum = 1;
        for (auto iter = arr.begin(); iter != arr.end();)
        {
            arr.insert(iter, left);
            for(int j = 0; j < iterNum; ++j)
                iter++;
            arr.insert(iter, right);
            
            iterNum++;
            left++;
            right--;
        }
        
        arr.push_front(i * 3);
        arr.push_front(2);
        arr.push_front(1);
        for (int j = i + 1; j < 2 * i + 2; ++j)
            arr.push_back(j);
    }
}