문제 설명
정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
제한 사항
- n은 1 이상 1,000 이하입니다.
입출력 예
| 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] |
접근
일단, 나는 이 문제를 푸는 데 실패했다. 내가 생각한 방식으로 알고리즘을 구현하려고 해도 할 수 없었고, 하루를 넘겨버렸기 때문에 결국 다른 사람의 풀이를 빌려 이 문제를 해결하고자 한다.
그럼에도 내가 접근한 방식을 기록해두는 것이 중요하다 생각해 남긴다. 접근법을 설명하기 위해 n = 4인 경우를 기준으로 설명한다.
-
1 ~ n까지는 인덱스 증가폭이 1씩 늘어난다.
1 -> 0
2 -> 1
3 -> 3
4 -> 6다음과 같이 숫자가 1 증가할 때마다 전 인덱스와의 증가폭도 1씩 늘어나고 있는 규칙이 있다.
-
n까지 저장했다면 n - 1번까지 연속적으로 저장
n까지 저장을 완료했다면 밑변에 온 것이므로 연속적으로 숫자를 저장하면 된다. 위의 경우 4까지 저장했으므로 5, 6, 7을 인덱스 7, 8, 9에 연속적으로 저장하면 된다. -
인덱스 2까지 -n, -(n - 1), ... 순으로 인덱스 감소
일단 밑변까지 했다면 2까지는 거꾸로 올라가면서 저장해야 하는데, 이때 인덱스의 감소 폭이 -n, -(n - 1), -(n - 2), ... 순으로 감소하는 것을 확인할 수 있다.7 -> 9
8 -> 5
9 -> 2
하지만, 여기서 문제는 이 한 번의 과정으로 끝나지 않고 한 번 이상 더 사이클을 돌아야 할 때 1번의 과정을 몇 번 진행하는지 정할 수 없었다는 점이다. n = 4라면, 1번만 진행되고, n이 5나 6이라면 2번 진행하는데, 그 점을 어떻게 구현해야할지 감이 오지 않았다.
다른 사람의 풀이
우선, 이를 1차원 배열로 해결하려고 했던 것이 잘못된 접근이었을 가능성이 있다고 생각한다. 밑변과 높이가 있으니 2차원 배열을 생각하는 것이 더 자연스러웠을텐데 말이다.
2차원 배열로 생각하고 인덱스를 계산해보면 다음과 같은 규칙을 얻을 수 있다.
01 [0][0]
02 09 -> [1][0] [1][1]
03 10 08 [2][0] [2][1] [2][2]
04 05 06 07 [3][0] [3][1] [3][2] [3][3]- 그럼 이때, 1 ~ n까지는 x값(행)만이 1씩 증가하는 것을 볼 수 있다.
- 밑변의 경우는 y값(열)만이 1씩 증가하는 것으 볼 수 있다.
- 이후 대각선을 채우는 경우는 x와 y값이 모두 -1씩 감소하는 것을 볼 수 있다.
문제는 어떤 과정을 언제 돌려야 할 지 결정할 수 있는 기준을 찾는 것이었다. 이때, 문제에서 제시한 3가지 삼각형을 보다 보니 n의 값만큼 위 세 작업 중 하나가 진행되는 것을 알 수 있었다.
그렇다면 range(n)의 값을 통해 각 과정을 구분할 수 있지 않을까 생각했고, 3개의 과정이 있으니 3으로 나눈 나머지 값을 활용하면 될 것이라 생각했다.
def solution(n):
answer = []
arr = [[0 for _ in range(i)] for i in range(1, n + 1)]
num = 1
x = -1
y = 0
for i in range(n):
for j in range(n - i):
if not i % 3:
x += 1
arr[x][y] = num
num += 1
elif i % 3 == 1:
y += 1
arr[x][y] = num
num += 1
else:
x -= 1
y -= 1
arr[x][y] = num
num += 1
return answer그래서, 앞서 얘기한 로직을 다음과 같이 구현했다. 문제에서는 1차원 배열로 반환하라고 하였으니 answer를 1차원 배열로 바꿔주면 된다.
for row in arr:
for x in row:
answer.append(x)나는 다음과 같은 방식으로 1차원 배열을 만들었다. 그런데 다른 사람의 풀이를 보니 다음과 같은 방식도 있었다.
return list(itertools.chain(*tri_snail))