[프로그래머스/코딩테스트/Python] 삼각 달팽이 문제풀이

프로그래머스 월간 코드 챌린지 시즌 1 삼각 달팽이 문제를 풀이해보았다.

 

초등학교 시절에 친구들과 했던 달팽이 놀이가 생각나기도 했다.

 

복잡해 보이기도 하지만 지속되는 패턴을 찾으면 생각보다 쉽게 풀 수 있다. (본인은 쉽지 않았다.)

 

그림을 그려보면서 풀면 더 쉽게 풀이가 가능하다.

 

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

코딩테스트 연습 - 삼각 달팽이

 

---

문제설명

정수 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

---

문제풀이

높이가 n인 삼각형 형태를 쌓고 안쪽으로 돌아가면서 숫자를 채우는 형태이다.

처음에는 숫자들을 리스트형태로 한 줄에 펼친 다음에 패턴을 찾아보았지만, 특정 패턴을 찾기는 쉽지 않았다.

 

삼각형 형태를 들여다보며 숫자를 채워보던 중, 한 가지 패턴을 발견했다.

바로 숫자를 채우는 방향이 바뀔때마다 움직이는 칸이 하나씩 줄어든다는 것이다.

n=6일 때, 6층을 쌓은 뒤 처음 오른쪽으로 진행할때는 5칸, 그 다음 위로 올라갈 때는 4칸 등 방향을 바꿀 때 마다

움직이는 범위(칸)가 한 칸씩 작아진다.

 

패턴을 알아냈으니 움직일 수 있는 삼각형을 먼저 만들어내기로 했다.

반복문을 통해서 리스트안에 리스트를 넣는 형태로 삼각형을 만들어냈다.

각 리스트안에 층의 수를 넣도록하면, 벌써 1부터 n까지의 한 줄은 끝났다.

또한, 방향을 맞추어 주기 위해서 방향을 알려주는 리스트를 만들기로 했다.

오른쪽(0), 위쪽(1), 아래쪽(2) 순이며, 삼각달팽이는 n-1번 방향을 바꾸므로, 리스트의 길이가 그 이상이면

반복문을 멈추고 저장하도록 했다.

 

움직일 칸 수(step)을 각 방향이 바뀔 때마다 1씩 줄게하였고,

각 방향에 움직일 때마다 해당 위치의 행과 열(row, column)을 파악해 다음숫자(count)를 넣어줬다.

(1부터 n까지는 삼각형을 만들 때 입력해주었기 때문에, step과 count의 초기값은 n과 같다.)

 

반복문이 끝나면, 다시 반복문을 통해 (반복문을 너무 많이 썼다.) 한 줄로 만들어준다.

 

def solution(n):
    row = n-1
    column = 0
    count = n
    step = n
    direction = []
    triangle_snail = []
    answer = []

    for i in range(1, n+1):
        triangle_snail.append([i]*i)

    for i in range(n):
        direction.extend([0,1,2])
        if len(direction) == n-1 or len(direction) > n-1:
            direction = direction[:n]
            break

    for direct in direction:
        step -= 1
        for steps in range(0,step):
            if direct == 0: # 오른쪽
                column += 1
                count += 1
                triangle_snail[row][column] = count
            elif direct == 1: # 위쪽
                column -= 1
                row -= 1
                count += 1
                triangle_snail[row][column] = count
            else: # 아래쪽
                row += 1
                count += 1
                triangle_snail[row][column] = count

    for s in range(0, n):
        answer.extend(triangle_snail[s])
        
    return answer

---

불필요하게 반복문을 많이 쓰기도 한 것 같다.

다른 사람의 풀이를 보니 훨씬 더 짧게 구현해 놓았다.

또한 방향을 알려주는 리스트를 쓸 필요없이, n % 3을 해주면 각 방향에 맞게 설정할 수 있었다.

 

다른 사람의 풀이

 

def solution(n):
    answer = [[0 for x in range(y)] for y in range(1, n + 1)]
    num = 1
    x = -1
    y = 0
    test = n % 3
    for i in range(n, 0, -1):
        for j in range(i):

            if n % 3 == test:
                x = x + 1
            elif n % 3 == (test - 1) or n % 3 == (test + 2):
                y += 1
            else:
                x -= 1
                y -= 1
            answer[x][y] = num
            num = num + 1

        n = n - 1

    import itertools
    return list(itertools.chain(*answer))