알고리즘 공부 12일차

1.  삼각 달팽이 (프로그래머스)

문제 설명

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

---

제한사항

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

---

입출력 예

nresult

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]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

 

---

해결 방법 : 

일단 먼저 숫자를 읽을때 3가지 경우로 나눈다. 내려올때, 오른쪽으로 갈때, 올라갈때, 이렇게 되어있으니 이걸 기점으로 좌표를 이동시긴다. 실제로는 밑의 그림처럼 좌표를 생각하고 풀면 된다.

 

n=4일때

01

02 09

03 10 08

04 05 06 07

 

이유 : 

이런 도형류 + 처음보는 문제는 그냥 손으로 규칙이나 알고리즘을 찾는게 베스트인 듯하다. 그걸 얼마나 빨리 찾느냐가 실력인듯.. 이번에는 거의 30분쯤 걸렸다. 규칙을 알고나서 어떻게 구현할지도 몰라서 꽤나 시간을 들이다가 결국 블로그를 찾아보게 되었다. 생각보다 간단했는데, 행렬로 트리를 만드는 것처럼하면서 좌표를 바꾸는 방법은 생각못했는데 좋은 것을 배운듯하다.

 

참고 자료 : coding-lks.tistory.com/56

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

 

def solution(n):
    res = [[0] * n for _ in range(n)]
    answer = []
    x, y = -1, 0
    num = 1

    for i in range(n):
        for j in range(i, n):
            #down
            if i % 3 == 0:
                x += 1
                
            #right
            elif i % 3 == 1:
                y += 1
                
            #up
            elif i % 3 == 2:
                x -= 1
                y -= 1
                
            res[x][y] = num
            num += 1
    # print(res)
            
    for i in res:
        for j in i:
            if j != 0:
                answer.append(j)
    return answer

 

---