프로그래머스(Python)/Level2

[프로그래머스] '삼각 달팽이' 알고리즘 풀이 - Python

Jinomad 2020. 10. 9. 22:26

Contents

  1. 문제 설명

    [제한사항]

    [입출력 예]
  2. 알고리즘 분석 

    [나의 풀이]

    [Most 1 의 풀이]

 

문제 설명

 

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

 

 

 

 

제한사항

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

 

 

입출력 예

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



알고리즘 분석

 

  • 나의 풀이
from itertools import chain

# 방향을 바꿔야하는지 확인하는 함수
def check(snail, h, w, point):
    h, w, s_len = h+point[0], w+point[1], len(snail) # 다음 좌표와 snail의 길이를 변수에 저장
    return h >= s_len or w >= s_len or snail[h][w] != 0

def solution(n):
    n_len = sum(range(1, n+1)) # 배열에 저장될 최대의 수를 구함
    snail = [[0] * i for i in range(1, n+1)] # n에 맞는 크기의 배열을 생성
    point = [(1, 0), (0, 1), (-1, -1)] # 좌표이동에 필요한 경우의 수는 3가지 
    h, w, i = 0, 0, 0 # 높이, 너비, 좌표이동 인덱스 

    for number in range(1, n_len+1): # 1 ~ n_len까지 반복 
        snail[h][w] = number # 배열에 number를 저장
        if check(snail, h, w, point[i]): # 방향을 바꿔야하는지 확인
            i = (i + 1) % 3 # 참이면 i를 바꾸는 것으로 방향을 전환 
        h, w = h + point[i][0], w + point[i][1] # 실제적으로 좌표이동 
    return list(chain(*snail)) # chain을 이용해서 리스트를 하나로 붙인다

 

오랜만에 문제풀이를 하니까 좀 버거웠다. 

딱히 어려울 것은 없는 문제였지만, 

chain이라는 함수를 알게되어서 리스트를 간편하게 이어줄 수 있었다.