코딩테스트 연습/프로그래머스

[프로그래머스 - Python] 코딩테스트 연습 > 월간 코드 챌린지 시즌1 > 삼각 달팽이 in python

슈퍼짱짱 2021. 1. 19. 16:06
반응형

파이썬으로 코딩테스트 연습 :: 프로그래머스 삼각 달팽이

 

    • 삼각 달팽이

문제 설명

정수 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

  • 문제 예시와 같습니다.

입출력 예 #3

  • 문제 예시와 같습니다.

 

programmers.co.kr/learn/courses/30/lessons/68645

 

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

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]

programmers.co.kr

 


 

Python Code

 

import numpy as np

def triangle(start,m) :
    if m == 1:
        return np.array([[start]])
    one = list(range(start, start+m))
    two = list(range(one[-1]+1, one[-1]+m))
    three = list(range(two[-1], two[-1]+(m-1))) + [start]
    three.reverse()

    temp = np.array([[0]*m]*m)
    temp[:,0] = one
    temp[m-1,1:] = two
    np.fill_diagonal(temp, three)
    return(temp)

def fun(m) :
    return sum([i+1 for i in range(m)])

def solution(n):
    m = n
    start = 1

    row = 0;col = 0

    matrix = np.zeros((n,n)).astype(int) ## 최종
    
    while matrix.max() < fun(m) :
        table = triangle(start,n)
        idx = np.tril_indices(n)
        table = table[idx]
        matrix[(idx[0] + row, idx[1] + col)] = table

        n = n-3
        start =np.max(table)+1
        row +=2
        col +=1
    
    answer = matrix[np.tril_indices(m)]
    return [int(i) for i in answer]

 

triangle 함수는 가장 바깥쪽 3면을 채워 numpy 형태 테이블로 출력해주는 함수이다.

 

예로 n=6이라 할 때 start = 1, m = 6으로 파라미터를 전달하면

one, two, three의 결과는 다음과 같다.

 

그림1

 

즉, 6 by 6 매트리스에서 각각 채워지는 부분은 다음과 같다. (정삼각형 형태가 아니라 아래방향 직각삼각형 형태로 구현했다.)

그림2

triangle 함수 실행시 결과이다.

 

그림3

 


이제 이 함수를 반복적으로 실행하여 아래 삼각형에 빈 부분을 모두 채워준다.

 

n=4 일 때 채워진 값들 중 가장 큰 값은 10이며 이는 4+3+2+1 과 동일하다.

n=5 일 때 역시 가장 큰 값은 15로 5+4+3+2+1 와 동일하다.

즉, while 문에 조건을 채워진 가장 큰 값이 n+(n-1)+(n-2)+...+1 보다 작다면 실행하도록 했다.

 

바로 위 [그림3] 에서 아래 삼각형 중 아직 채워지지 않은 부분을 채워주기 위해 triangle 함수를 한 번 더 호출한다.

start는 16(=현재 채워진 값 중 가장 큰 값 + 1)으로, m은 이제 3층만 필요하므로 3=(n-3)으로 파라미터를 전달한다.

 

결과는 다음과 같다.

 

그림4

 

이결과를 위 [그림3] 아래 삼각형 중 비어있는 부분에 채워주면 다음과 같다.

 

그림5

 

이 결과를 np.tril_indices() 함수를 활용하여 아래 삼각형 부분만 1차원으로 출력해주면 된다.

 

단, 결과를 int형으로 바꾸어주지 않으면 type error가 발생하기 때문에 [int(i) for i in answer] 를 추가해주었다.

 


numpy 에서 대각선을 채우는 numpy.fill_diagonal() 에 대한 설명은 아래를 참고한다.

2021/01/19 - [Python] - [numpy tutorial] numpy에서 대각선 값 채우기 in python

 

[numpy tutorial] numpy에서 대각선 값 채우기 in python

Python :: fill diagonal in numpy numpy에서 대각선 값을 채우기 위해서는 numpy.fill_diagonal() 를 활용하면 된다. numpy를 np 로 import 하고, 0부터 15로 이루어진 4 by 4 테이블을 생성해 주었다. import nu..

leedakyeong.tistory.com

 

반응형