[프로그래머스 lv2] 삼각 달팽이

월간 코드 챌린지 시즌1 문제입니다.

---

문제 설명

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

제한사항

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

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

---

나의 풀이

주어진 문제는 단순한데 이걸 어떻게 해결해야 할 지 많이 고민했고 그 만큼 시간이 오래 걸린 문제이다.

문제처럼 순서대로 빙글 빙글 돌아가며 숫자를 넣기에는 리스트 중간에 숫자를 삽입해야 하는 경우가 자주 발생해 상당한 비효율성을 초래할 것이기 때문에 다른 방법이 필요했다.

그나마 그런 비효율성을 낮추기 위해서는 무조건 리스트의 끝에 넣어야 했다.

그래서 나는 빙글 빙글 돌아가는 순서가 아닌 다음과 같은 순서를 따랐다.

이렇게 왼쪽, 바닥, 오른쪽 순으로 하면 항상 리스트의 끝에만 추가할 수 있다.

 

그리고 시작 점과 닫히는 점의 정보를 담기위해 deque을 사용했다.

n=6일 때 시작 점은 1, 16이 되고, 닫히는 점은 21, 12가 된다. 이때 시작 점은 가장 왼쪽부터 추가되어야 하기 때문에 작은 수가 우선으로 와야하고, 닫히는 점은 안쪽부터 닫혀야 리스트에 차례대로 들어갈 수 있기 때문에 큰 수가 먼저 와야한다.

시작 점에 저장되는 정보는 시작 점의 숫자와 길이이다.

start 큐

n=6일 때 (1, 6), (16, 3)이 되겠다. 시작 점의 인덱스는 0부터 시작하여 2씩 커진다.

1번 왼쪽 면

시작 점에 담긴 정보를 바탕으로 위 그림에서 1번에 해당하는 부분을 구현한 코드는 다음과 같다.

1번 코드

2번 바닥 면

바닥 부분은 answer의 가장 끝 숫자보다 하나 큰 숫자부터 시작해서 count-1개를 추가하면 된다.

그 코드는 다음과 같다.

2번 코드

3번 오른쪽 면

오른쪽 면은 삼각형의 크기가 3 이상일 때만 존재할 수 있다.

삼각형의 크기가 2이면 왼쪽 면과 오른쪽 면 만으로 삼각형이 완성되기 때문이다.

그리고 오른쪽 면의 길이는 바닥면보다 1 작다.

그래서 오른쪽 면의 시작 인덱스는 바닥 면 바로 위쪽이고, 개수는 바닥면-1이 된다.

이 위치, 개수 정보를 close 큐에 저장한다.

close 큐 정보

위에서 설명했듯이 오른쪽 면은 안쪽부터 채워져야 하기 때문에 위치가 더 높은 것이 우선이 된다. 그래서 start와 다르게 close는 popleft()가 아닌 pop()을 해서 오른쪽 부터 꺼내 써야한다.

시작 숫자는 오른쪽 면 시작점 밑의 마지막 숫자 + 1이다.

3번 코드

문제에서는 answer을 이중 리스트가 아닌 하나의 리스트에 모든 값이 순서대로 들어간 것을 요구했기 때문에

sum(answer, [])

로 반환하면 정답이 된다.

전체 소스코드

from collections import deque

def solution(n):
    num = n
    start = deque([(1, num)])
    close = deque()
    while num > 3:
        start.append((start[-1][0]+3*num-3, num-3))
        num -= 3
        
    answer = [[] for _ in range(n)]
    idx = 0
    while start:
        startNum, count = start.popleft()
        num = startNum
        for j in range(count):
            answer[idx+j].append(num)
            num += 1
        bottom = [i+answer[idx+count-1][-1] for i in range(1, count)]
        answer[idx+count-1].extend(bottom)
        if len(bottom) > 1:
            close.append((idx + count - 2, len(bottom)-1)) # 위치, 개수
        idx += 2
    while close:
        idx, count = close.pop()
        num = answer[idx+1][-1]+1
        for i in range(count):
            answer[idx-i].append(num)
            num += 1
    print(answer)
    return sum(answer, [])

 

테스트 결과