[문제]
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,[])
'알고리즘 > 알고리즘 문제' 카테고리의 다른 글
| [python] 프로그래머스 > 2016 (0) | 2021.01.07 |
|---|---|
| [python] 프로그래머스 > 문자열 > 이상한 문자 만들기 (0) | 2021.01.06 |
| [python] 프로그래머스 > 월간 코드 챌린지 > 삼각 달팽이 (0) | 2021.01.06 |
| [python] 프로그래머스 > 스킬트리 (0) | 2021.01.05 |
| [python] 프로그래머스 > 탐욕법(Greedy) > 체육복 (0) | 2021.01.05 |
| [python] 프로그래머스 > 문자열 > 문자열 내 마음대로 정렬하기 (0) | 2021.01.04 |