[programmers][월간 코드 챌린지 시즌1] 삼각 달팽이

문제 : programmers.co.kr/learn/courses/30/lessons/68645

---

정수 n이 주어질 때 밑변, 높이가 n인 삼각형을 반시계 방향으로 달팽이 채우기를 진행한 배열을 구해라.

ex) n = 3

1

2 6

3 4 5

---

queue, stack을 이용했다.

n, n-1, n-2, n-3 ... 1 개씩 배열을 아래, 오른쪽, 위로 채워나간다.

이때, 아래, 오른쪽을 채울 때는 수를 큐에 넣고 위에 넣을 때는 스택에 넣는다.

높이가 n인 삼각형이므로 크기가 n인 queue 배열, stack 배열 2개가 필요하다.

queue[i], stack[i] 에는 삼각형의 i형에 들어갈 수를 저장한다.

모든 배열을 채웠을 때, 

i를 처음부터 끝까지 탐색하면서 queue에 있는 수를 먼저 넣고 stack에 있는 수를 이 다음에 넣는 식으로 정답 배열을 만들어 나간다.

n = 5일 때를 예를 들면

index	queue	stack
0	1
1	2	12
2	3 13	11
3	4 14	15 10
4	5 6 7 8 9

위와 같이 배열이 채워지고 이를 배열로 만들면

1

2 12

3 13 11

4 14 15 10

5 6 7 8 9 

가 된다.

 

시간복잡도는 n, n-1, ... 2, 1을 더한만큼 들므로 O(N^2 / 2).

 

이렇게 해도 되고 그냥 2차원 배열 하나둬서 겉부터 채워나가는 식으로 채운다음, 정답 배열을 만들 때는 안채워진 부분은 삭제하는 식으로 해도 된다. 이렇게하면 안채워진 부분은 삭제해야 하므로 O(N^2)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C1/%EC%82%BC%EA%B0%81%20%EB%8B%AC%ED%8C%BD%EC%9D%B4.cpp