320x100
문제 : 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)
320x100
'알고리즘 문제 > Programmerse' 카테고리의 다른 글
[programmers][월간 코드 챌린지 시즌1] 3진법 뒤집기 (0) | 2020.10.17 |
---|---|
[programmers][월간 코드 챌린지 시즌1] 짝수 행 세기 (0) | 2020.09.20 |
[programmers][월간 코드 챌린지 시즌1] 풍선 터트리기 (0) | 2020.09.17 |
[programmers][월간 코드 챌린지 시즌1] 두 개 뽑아서 더하기 (0) | 2020.09.15 |
[programmers][찾아라 프로그래밍 마에스터] 폰켓몬 (0) | 2020.09.13 |
댓글