사용자 도구

사이트 도구


ps:problems:programmers:68645

삼각 달팽이

ps
링크https://programmers.co.kr/learn/courses/30/lessons/68645
출처프로그래머스
문제 번호68645
문제명삼각 달팽이
레벨Level 2
분류

구현

시간복잡도O(n^2)
인풋사이즈n<=1000
사용한 언어Python
해결날짜2020/12/17

풀이

  • 그냥 구현 문제
  • 삼각형 형태의 2차원 리스트에 채우고 이어 붙이는 방법도 가능하지만, 1차원 리스트에 바로 채우는 방식으로 했다.
  • 1차원 리스트을 삼각형 모양으로 가정하고 채우려면 조금 번거롭다. 예를 들어, 맨 처음 아래쪽으로 채워 나갈때도, 인덱스가 0, 1, 3, 6, … 이런식으로 일정하지 않게 증가하게 되기 때문에 현재 행 번호를 구해서 인덱스를 증가시켜야 하니 구현이 번거롭다.
  • 대신 1차원 리스트를 사각형 모양으로 가정하고, 그 중에 삼각형만큼만 채운 다음, 마지막에 채워진 원소들만 남기고 나머지를 제거하는 방식으로 구현했다.
    • 이러면 일정하게 아래로 채울때는 인덱스가 n씩 증가, 오른쪽일때는 1씩 증가, (대각선)위쪽일때는 n+1씩 감소한다.

코드

"""Solution code for "Programmers 68645. 삼각 달팽이".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/68645
- Solution link: http://www.teferi.net/ps/problems/programmers/68645
"""


def solution(n):
    step_d, step_r, step_u = n, 1, -(n + 1)
    next_step = {step_d: step_r, step_r: step_u, step_u: step_d}
    answer = [0] * (n * n)
    step = step_d
    index = 0
    answer[index] = 1
    for i in range(2, n * (n + 1) // 2 + 1):
        if index + step >= len(answer) or answer[index + step]:
            step = next_step[step]
        index += step
        answer[index] = i
    return [x for x in answer if x]

토론

댓글을 입력하세요:
E F H F V
 
ps/problems/programmers/68645.txt · 마지막으로 수정됨: 2021/01/21 16:22 저자 teferi