본문 바로가기
매일매일 코딩연습!/프로그래머스

[코딩연습 11일차] 프로그래머스 : 삼각 달팽이 / python풀이 java풀이

by k-bonnie 2021. 2. 13.
728x90

🐌🐌🐌🐌후기: 달팽이 문제 아니랄까봐 풀이가 달팽이마냥 느렸음. 이것도 수학문제 느낌 낭낭^^....

 


문제 설명

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

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


제한사항

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

입출력 예

n result
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]


내 풀이>> 와,, 그림으로 이해하니까 훨씬 쉬웠다. 알고리즘 생각해내고 코딩다하는데 3시간 걸린건 안비밀^_^

근데 풀이에 올리려고 마우스로 그림그리는건 제일 어려웠음ㅋㅋㅋㅋ

 

1. 그냥 직관적으로 생각하면 n행의 삼각형 위에서 화살표 진행 방향이 세군데임. "아래" "오른쪽" "위"

또한 n행인 삼각형은 총 n번의 화살표를 긋는다!!!

그런데 프로그래밍은 '0'번이 시작 순서이기 때문에 0~n-1번의 화살표가 생김.

for i in range(n):

 

2. 또한 i번째 화살표에 들어가는 숫자의 갯수를 j라고 하면, j =  n-i개 이다. 처음에 이중 for문으로 작성하자

for j in range(i, n):

 

3. 화살표는 아래방향을 첫번째 시작으로 오른쪽, 위쪽이 반복됨 & 턴은 3이 주기 

  그러므로 i % 3 == 0이면 아래, 1이면 오른쪽, 2이면 위쪽

☞ if i % 3 == 0 : ↙조건

    elif i % 3 == 1: →조건

    elif i % 3 == 2: ↖조건

 

4. 행렬에서 좌표로 움직여야하므로, 좌표를 (row, col)이 움직이는 규칙은

  ↙조건row +1

  →조건:  col +1

  ↖조건:  row -1, col -1

   (((단, 화살표 시작하고 움직인 첫칸이 (0,0)으로 시작해야해서 초기값을 row = -1, col = 0 으로 시작한다.)))

 

5. 이렇게 진행되는 좌표마다 N=1, N+=1인 정수를 넣어줍시다.

 

6. 만들어진 2차원 행렬을 1차원 list로 풀어냅시다 (chain함수 사용)

 

from itertools import chain

def solution(n):
    
    triangle= [[0]* i for i in range(1, n+1)] #총n행을 가지고, n번째 행에는 n칸인 삼각형 틀 정의하기.
    row = -1
    col = 0 #초기 좌표값 설정
    
    N = 1 #빈칸에 들어갈 숫자 초기 N정의해주기
    
    for i in range(n): #n행인 삼각형에서 화살표의 순서 i를 인덱싱, 화살표는 0번부터 n-1번
        for j in range(i,n): #한 화살표에 들어가는 숫자갯수 (n-i)개를 인덱싱
            
            if i % 3 == 0: #화살표 순서가 0,3,6... 이면 아래로가는 화살표
                row += 1
            elif i % 3 == 1: #화살표 순서가 1,4,7... 이면 오른쪽으로 가는 화살표
                col += 1
            elif i % 3 == 2: #화살표 순서가 2,5,8... 이면 위로가는 화살표
                row -=1
                col -=1
            
            triangle[row][col] = N #위 조건에 맞는 칸에 N을 저장해 줌.
            N += 1 
                
    return list(chain(*triangle)) #결과값 2차원행렬을 1차 배열list로 반환.

 

 

끗....

오래걸렸다....

힘들다.........

얘를 java로 변형해 보고 싶은데.. 그건 내일 해서 추가해야 겠다.


Java풀이>>

 

다른 것들을 java식으로 코딩하는것은 일찍 했는데

2차원 배열을 1차원 배열(list)로 반환하는 방법을 찾는데 힘들어서,, 다른 분의 정답을 참고함.

 

파이썬에는 chain함수로 list로 풀어낼 수 있었으나, java에서는

일단 return해줄 결과값 answer을 1차원 배열(list)으로 선언해 준다.

이때 list의 길이는 n행 삼각형의 총 숫자 갯수,  n*(n+1))/2으로 선언해 준다.

(예) 4행 삼각형이면 총 숫자 갯수 = 1+2+3+4 = 4(4+1)/2

 

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[(n*(n+1))/2]; //return해줄 1차원 배열 list선언
        int[][] triangle = new int[n][n]; //n행삼각형(사실 이거는 사각형)의 틀인 2차배열 선언하기
		
        /*
        우리가 선언한 2차원 배열중에 사용될 부분을 그려보면 다음과 같음.
        [/]부분이 사용되는 부분, [0]부분이 사용 안되는 부분
        
        ex. n=5일때
        [/][0][0][0][0]
        [/][/][0][0][0]
        [/][/][/][0][0]
        [/][/][/][/][0]
        [/][/][/][/][/]
        
        */
        int N = 1; //배열에 들어갈 숫자 시작점
        int row = -1; //배열의 첫 행 시작점
        int col = 0; //배열의 첫 열 시작점
        

        for (int i = 0; i < n; i++) { //화살표의 순서뽑기.
            for (int j = i; j < n; j++) { //화살표안의 숫자 갯수 뽑기
                if (i % 3 == 0) {
                    row++;
                } else if (i % 3 == 1) {
                    col++;
                } else if (i % 3 == 2) {
                    row--;
                    col--;
                }
                triangle[row][col] = N++;
            }
        }
		
        //출력과정
        int k = 0; //1차원 배열(list)에 들어갈 배열 넘버
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(triangle[i][j] == 0) break; 
                //2차원 배열이고 우리는 삼각형 모양만 썼고, 위 설명처럼 안쓰인 반쪽이 있다. 
                //그래서 그런 부분을 만나면 break해서 1차원 배열에 저장 안되게 한다.
                answer[k++] = triangle[i][j];
            }
        }

        return answer;
    }
}

 

 

찐으로 끝!!!!!!!!