삼각 달팽이(python)

30 Oct 2020 in Algorithm on Algorithm, Programmers, 시뮬레이션, Python

참고자료

tjdud0123님의 블로그
프로그래머스 - 삼각 달팽이

문제 설명

정수 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,8,9,10,11]

나의 생각

answer = [[]] * n

빈 배열을 n 만큼 만들어서 index를 조절하면서 append하면 되겠다고 생각했다.
그래서 규칙을 찾으려고 했지만 실패했다.

솔루션

달팽이가 움직이는 방향은 아래, 오른쪽, 위 이렇게 3가지 방법밖에 없다. 달팽이가 움직이는 범위는 왼쪽으로 당겨서 생각하면 편하다.

[[1],
 [2, 12],
 [3, 13, 11],
 [4, 14, 15, 10],
 [5,  6,  7,  8,  9]]

이렇게 생각하면 방향을 바꾸는 경우는 3가지다.

1. 행이 n을 초과하는 경우
2. 열이 행을 초과하는 경우
3. 숫자가 이미 존재하는 경우

0행 0열, 아랫방향으로 시작한다.
달팽이가 범위 안에 있으면 그대로 방향에 따라 움직이고
달팽이가 범위 밖으로 나가면 방향을 바꿔주고
바꾼 방향으로 움직인다.

코드

1. 첫번째 코드 *를 사용한 점과 함수를 사용한 점에서 색다르다.

import itertools
# 달팽이가 움직인 좌표
def get_next(x, y, d):
    DELTAS = {'up': (-1, -1), 'down': (1, 0), 'right': (0, 1)}
    dx, dy = DELTAS[d][0], DELTAS[d][1]
    nx, ny = x + dx, y + dy
    return nx, ny
# 달팽이가 범위 안에 있는지 밖에 있는지 확인
def check_turn(nx, ny, n, snail):
    return nx < 0 or nx >= n or ny > nx or snail[nx][ny] != 0

def solution(n):
    NEXT = {"up" : "down", "down" : "right", "right" : "up"}
    snail = [[0] * i for i in range(1, n + 1)]
    N = sum(range(1, n + 1))
    x, y, d = 0, 0, "down"

    for num in range(1, N + 1):
        snail[x][y] = num
        if check_turn(*get_next(x, y, d), n, snail):
            d = NEXT[d]
        x, y = get_next(x, y, d)

    return list(itertools.chain(*snail))

1. 두번째 코드 BFS와 비슷한 방법이다.
   하지만 모든 경우를 판단하는 것이 아니기 때문에 시뮬레이션이라고 보는 것이 맞다고 생각한다.

def solution(n):
    answer = []
    # 아래, 오른쪽, 위
    dx = [1, 0, -1]
    dy = [0, 1, -1]
    #  1~n까지의 합
    N = (n + 1)* n // 2
    snail = [[0] * i for i in range(1, n + 1)]
    x, y, d, num = 0, 0, 0, 1

    while(num <= N):
        snail[x][y] = num
        num += 1
        nx = x + dx[d]
        ny = y + dy[d]
        # 범위 안에 있는 경우
        if 0 <= nx < n and 0 <= ny <= nx and snail[nx][ny] == 0:
            x = nx
            y = ny
        # 범위 밖으로 나간 경우
        else:
            d = (d + 1) % 3
            x += dx[d]
            y += dy[d

    return sum(snail, [])

몰랐던 지식

3.

*get_next(x, y, d)

함수 앞에 *(별 표시)가 있어서 포인터인가 검색해봤다.
파이썬에서는 *는 여러 개의 인수를 받을 때 사용한다.

def hello((*args, **kwargs)):

*args는 hello의 인자들을 개수 상관없이 튜플 형식으로 전달해준다.
**kwargs는 hello의 인자들을 개수 상관없이 딕셔너리 형태인 {“키워드” : “특정값”}으로 전달해준다.

3.

sum(snail, [])

이 경우 어떻게 2차원 배열에서 1차원 배열의 합으로 표현이 되는지 잘 모르겠다.
그래서 python 공식문서에서 sum을 찾아봤다.

sum(iterable, /, start=0)

start 및 iterable 의 항목들을 왼쪽에서 오른쪽으로 합하고 합계를 돌려줍니다.
iterable 의 항목은 일반적으로 숫자며 시작 값은 문자열이 될 수 없습니다.
어떤 경우에는 sum() 에 대한 좋은 대안이 있습니다.
문자열의 시퀀스를 연결하는 가장 선호되고 빠른 방법은 ‘‘.join(sequence) 를 호출하는 것입니다.
확장된 정밀도로 부동 소수점 값을 더하려면 math.fsum() 를 보세요.
일련의 이터러블들을 연결하려면 itertools.chain() 를 고려해보세요.
새롭게 알게 된 사실은 iterable 항목은 일반적으로 숫자라는 것이다.

3.

itertools.chain(*snail)

sum을 통해서 itertools.chain()도 찾아보았다.

itertools.chain(*iterables)

첫 번째 이터러블에서 소진될 때까지 요소를 반환한 다음 이터러블로 넘어가고,
이런 식으로 iterables의 모든 이터러블이 소진될 때까지 진행하는 이터레이터를 만듭니다.
여러 시퀀스를 단일 시퀀스처럼 처리하는 데 사용됩니다.

def chain(*iterables):
  # chain('ABC', 'DEF') --> A B C D E F
   for it in iterables:
       for element in it:
           yield element

• 코드 해석
  • iterables를 돌아가면서 yield를 해줌으로써 각 요소를 return 해줄 수 있다.
  • chain("ABC", "DEF")를 예를 들면
  • iterables에는 “ABC”와 “DEF”가 있어서
  • it은 “ABC”, “DEF를 의미한다.
  • element는 “A”, “B”, “C” 그리고 “D”, “E”, “F”를 의미한다.
  • 그리고 각 element 값을 return 해준다.
  • yield는 값을 리턴해주지만 함수를 끝내지 않는다.

차원을 모두 없애는 메소드라고 생각된다.
한 개의 차원을 줄여준다고 생각하면 될 듯하다.
코드를 보면 2차원을 줄여주지만 return이 객체이므로
객체를 리스트로 바꿔서 보여주면 결국 한 개의 차원을 줄여준다고 볼 수 있다.

더 알아볼 지식

iterable
iterator
generator
yield
파이썬- 기본을 갈고 닦자! 여기서 찾아보자.