본문 바로가기

알고리즘/알고리즘 문제

[python] 프로그래머스 > 월간 코드 챌린지 > 삼각 달팽이

[문제]

1. 문제 설명

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

 

 

2. 제한사항

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

 

3. 입출력 예

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]

 

[나의 풀이]

def solution(n):
    answer = []
    num = 1
    x = -1
    y = 0
    triangle = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(i, n):
            if i % 3 == 0:
                x += 1
            elif i % 3 == 1:
                y += 1
            elif i % 3 == 2:
                x -= 1
                y -= 1
            triangle[x][y] = num
            num += 1
            
    for tri in triangle:
        for t in tri:
            if t != 0:
                answer.append(t)
    return answer

- 도저히 어떤 규칙이 있는지 모르겠어서 찾아보고 겨우 이해했다.

- 삼각형이기 때문에 3으로 나눈다.

- n만큼 내려간 다음, n-1만큼 오른쪽으로 이동하고, n-2만큼 대각선으로 이동하는 규칙이 있다.

- 그렇기 때문에 이중for문을 사용한다.

- 이중 for문을 담을 그릇인 triangle을 저런식으로 초기화 시켜 줘야 한다.

 

 

[다른 사람의 풀이]

def solution(n):
    dx=[0,1,-1];dy=[1,0,-1]
    b=[[0]*i for i in range(1,n+1)]
    x,y=0,0;num=1;d=0
    while num<=(n+1)*n//2:
        b[y][x]=num
        ny=y+dy[d];nx=x+dx[d];num+=1
        if 0<=ny<n and 0<=nx<=ny and b[ny][nx]==0:y,x=ny,nx
        else:d=(d+1)%3;y+=dy[d];x+=dx[d]
    return sum(b,[])