본문 바로가기

Algorithm/Programers - C++

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

 

Level. 2

 

 

문제

 

정수 n이 매개변수로 주어집니다.

다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후,

첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

 

제한사항

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

 

풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    int arr[n][n];
    int r = n;
    int x = 0, y = 0;
    int count = 1;
    while(r > 0){
        for(int i=0; i<r; i++){
            arr[y+i][x] = count++;
        }
        for(int i=1; i<r; i++){
            arr[y+r-1][x+i] = count++;
        }
        for(int i=1; i<r-1; i++){
            arr[y+r-1-i][x+r-1-i] = count++;
        }
        r -= 3;
        y += 2;
        x += 1;
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<=i; j++){
            answer.push_back(arr[i][j]);
        }
    }
    
    
    return answer;
}

 

 

해결방법

1. n*n 크기의 배열을 만든다.

2. 위 그림을 왼쪽정렬한 것 같은 형태로 달팽이 채우기를 하며 데이터를 쌓아간다

    - 한번 테두리를 채울 때마다 3번 회전하므로 for문 3개를 이용해 테두리를 채워주었다. 

    - 테두리가 위로는 2겹, 아래로는 1겹 채워지므로 y-2, x-1, 회전의 기준이 되는 r은 -3 해주었다. 

 

 

 


다른 풀이

#include <string>
#include <vector>
using namespace std;
int arr[1000][1000];
vector<int> solution(int n) {
    vector<int> answer;
    int p = n;
    int k = 1;
    int x = -1, y = 0;
    for (int i = 0; i < n; i++) {
        for (int j = p;j >= 1; j--) {
            if(i%3==0) {
                arr[++x][y] = k;
            } else if (i % 3 == 1) {
                arr[x][++y] = k;
            } else if (i % 3 == 2) {
                arr[--x][--y] = k;
            }
            k++;
        }
        p--;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i;  j++) {
            answer.emplace_back(arr[i][j]);
        }
    }

    return answer;
}

 

 

방향 바꾸기는 총 n 번 실행되고, 회전할 때마다 해당 방향으로 채워야 하는 데이터 p가 1개씩 줄어든다. 

이 사실을 활용해서 for문을 사용해 배열을 만들어 주었다!

배열을 만드는 과정이 더 간단하고 가독성 있어 보인다 

 

 

 


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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr