코딩테스트--삼각달팽이(프로그래머스/C++)

https://programmers.co.kr/learn/courses/30/lessons/68645?language=cpp

코딩테스트 연습 - 삼각 달팽이

---

문제 설명

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

---

제한사항

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

---

입출력 예nresult

4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

---

문제는 되게 간결하네요??

 

요약하면

1. 젤위에서부터 숫자를 쌓아 만들꺼다-->이게 중요

2. 쌓아놓은걸 위에서 부터 출력해라

 

인 것 같네요

 

쌓여지는 규칙은 위에 처럼 내려와서 옆으로 간다음 다시올라가는걸 반복하네요!

 

처음에는 저 숫자들간의 규칙을 찾아보려했으나... 규칙은 있는데 만들어 보기가 쉽지않네요;;

 

그래서 저 피라미드를 직접 쌓아보기로 했습니다!

 

 

ㄱㄱㄱ

일단 피라미드를 배열로만들어 저장할껀데 위의 그림 모양이 아닌 왼쪽으로 붙인모양? 이될꺼에요

 

1

2 15

3 16 14

4 17 21 13 

5 18 19 20 12

6  7   8  9 10 11

 

이런모양!

 

일단 이걸 넣을 배열을 하나 만들어봅시다.

 

int list[n+1][n+1];
memset(list, 0, sizeof(list));

n+1 * n+1 배열을 만들어주고 초기화 해줍시다!

그러면

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0 

0 0 0 0 0 0 0

이런 배열이 생길꺼고 여기다 이제 숫자를 넣어줄꺼에요

 

 

총 몇개를 넣어야하는지도 구해줍시다.

    int allnum=0; //총 상자?의갯수
    for(int i=1;i<=n;i++){
        allnum+=i;
    }

여기까지했다면 이제 규칙을 찾아봅시다

 

위의 사진을 다시보면 규칙은

1. 내려오는거

2. 옆으로 가는거

3. 위로 다시올라가는거

 

이렇게 3개만 구해서 계속 반복해주면 될것 같네요

 

저는 배열을 좌표? 식으로 사용할꺼라서

int count=0;//박스 세어주기

int index1=0;//x
int index2=-1;//y

변수생성해주고

 

 

첫번째 규칙! 밑으로 내려가면서 +1

      for(int i=0;i<n;i++){
            index2+=1;
            if(list[index2][index1]==0){
                list[index2][index1]=count+1;
                count+=1;
            }
            else{
                index2-=1;
                break;
            }
        }

index1은 가만히있고

index2만 증가해주면서 비어있는지 확인!(if)

만약에 숫자가 있다? 바로 멈춰주고 마지막넣은자리로 돌아갑시다(else)

 

 

두번째 규칙! 옆으로 이동!

       for(int i=0;i<n-1;i++){
            index1+=1;
            if(list[index2][index1]==0){
                list[index2][index1]=count+1;
                count+=1;
            }
            else{
                index1-=1;
                break;
            }
        }

이번엔

index2은 가만히있고

index1만 증가해주면서 비어있는지 확인!(if)

만약에 숫자가 있다? 바로 멈춰주고 마지막넣은자리로 돌아갑시다(else) 어케 똑같네요 ㅎㅎ...

 

 

마지막 규칙! 대각선으로 올라가기!

     for(int i=0;i<n-2;i++){
            index1-=1;
            index2-=1;
            if(list[index2][index1]==0){
                list[index2][index1]=count+1;
                count+=1;

            }
            else{
                index1+=1;
                index2+=1;
                break;
            } 
        }

 

이번엔 둘다 가소 해주면서 대각선왼쪽으로 올라가줍시다!

역시 숫자를 만나면 마지막자리로 돌아가기!(else)

 

 

위의 규칙들을 while문에 넣어서 count가 쌓아야하는 상자갯수가 될때까지 돌리면됩니다 ㅎㅎㅎ

while(count!=allnum){

	//여기에 규칙들!!

}

 

 

 

그리고 배열 순서대로 answer(벡터)에 추가해주시면 됩니다!!

  for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if (list[i][j]==0){
                break;
            }
            else{
                answer.push_back(list[i][j]);
            }
        }
    }

 

그대로 출력하시면 끝!!!

 

 

All

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

vector<int> solution(int n) {
    vector<int> answer;
    int list[n+1][n+1];
    
    memset(list, 0, sizeof(list));
    
    int allnum=0;
    for(int i=1;i<=n;i++){
        allnum+=i;
    }
    
    int count=0;
    int index1=0;
    int index2=-1;
   
    while(count!=allnum){
        for(int i=0;i<n;i++){
            index2+=1;
            if(list[index2][index1]==0){
                list[index2][index1]=count+1;
                count+=1;
            }
            else{
                index2-=1;
                break;
            }
        }
        
        for(int i=0;i<n-1;i++){
            if(count==allnum){
                break;
            }
            
            index1+=1;
            if(list[index2][index1]==0){
                list[index2][index1]=count+1;
                count+=1;
            }
            else{
                index1-=1;
                break;
            }
        }

        
        
        for(int i=0;i<n-2;i++){
            index1-=1;
            index2-=1;
            if(list[index2][index1]==0){
                list[index2][index1]=count+1;
                count+=1;

            }
            else{
                index1+=1;
                index2+=1;
                break;
            } 
        }
        
        
     }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if (list[i][j]==0){
                break;
            }
            else{
                answer.push_back(list[i][j]);
            }
        }
    }
    
    
    return answer;
}

줄일수 있을꺼같은데 기네요 ㅎ...

 

 

 

 

틀린 점이 있다면 댓 달아주세요!