1. 삼각 달팽이

문제 링크:
https://programmers.co.kr/learn/courses/30/lessons/68645?language=python3

1.1 내 풀이

시도1 : (실패) 인덱스를 바꿔가며 더하고 빼는 규칙

• [0,0],.., [3,0] 3까지 도달했으니 인덱스 바꿔서 +1
• [3,1],...,[3,3] 3까지 도달했으니 인덱스 바꿔서 -1
• [2,2],[1,1],[0,0] 이미 방문했던 [0,0]은 지우고, 1까지 도달했으니 마지막으로 [2,1] ??
• 규칙 파악이 어려움. 코드 안 돌아감.

def solution(n):
    # [[0,0], [1,0], [1,1], [2,0], [2,1], [2,2],...]
    q = []
    for i in range(n+1):
        q.extend([[i, k] for k in range(i+1)])
    
    now = [0,0]
    index = 0 # 처음에는 인덱스 0번째부터 늘어남. 
    answer = [] # 달팽이 채우는 인덱스

    while q:
        if now in q:
            q.remove(now)
            answer.append(now)
        now[index] += 1
        if now not in q: # q에 포함되어 있지 않으면
            now[index] -= 1 # 원래대로 돌려놓는다.
            index = (index+1)%2 #인덱스 체인지
        if now[0] < now[1]:
            
            
        
        
    return q

시도2 : 방향이 반복되는걸 반영

• 방향이 아래, 오른쪽, 위,...로 반복됨. move 함수 생성
• n 이 100 이상일 때 시간초과 뜸. 정렬때문에 n이 늘어날수록 급격하게 시간 늘어나는 것 같음.
• 테스트케이스 3개 런타임 오류남. 길이가 (n+1)*n//2이기 때문에 n이 100이상만 되어도 시간 오래걸릴듯

def solution(n):
    
    def move(x, y, direction):
        if direction == 0: # 아래
            return [x+1, y]
        elif direction == 1: # 오른쪽
            return [x, y+1]
        else: # 위
            return [x-1, y-1]
        
    total = (n+1)*n//2
    now = [0, 0]
    q = [now] 
    direction = 0
    for i in range(1, total):
        tmp = move(now[0], now[1], direction)
        if n in tmp or tmp[0]<tmp[1] or tmp in q:
            direction = (direction+1)%3
        now = move(now[0], now[1], direction)
        q.append(now)

    for i in range(len(q)):
        q[i].append(i+1) 
    q.sort(key= lambda x: (x[0], x[1]))
    answer = [x[2] for x in q]
    
    
    return answer

1.2 다른 사람 코드 참조

• [[1], [2, 9], [3, 10, 8], [4, 5, 6, 7]] 을 구하고 sum(answer,[])으로 2차원을 1차원으로 줄였다.(방법 여러가지. 아래 참조)

def solution(n):
    
    def move(x, y, direction):
        if direction == 0: # 아래
            return x+1, y
        elif direction == 1: # 오른쪽
            return x, y+1
        else: # 위
            return x-1, y-1
        
    x,y = 0, 0
    num = 1
    direction = 0
    answer = [[0]*i for i in range(1, n+1)]
    while num <= (n+1)*n//2:
        answer[x][y] = num
        nx, ny = move(x,y,direction)
        num += 1
        
        #0<=ny<=nx<n이고 아직 채우기 전이라면
        if 0<=nx<n and 0<=ny<=nx and answer[nx][ny] == 0: 
            x,y = nx,ny
        else:
            direction = (direction+1)%3
            x,y = move(x,y,direction)
            
    return sum(answer,[])

참고) 2차원 리스트를 1차원 리스트로 만들기

📍 참조 링크 : https://programmers.co.kr/learn/courses/4008/lessons/12738
(https://programmers.co.kr/learn/courses/4008)

반복문을 이용해 리스트를 더해갈 수도 있지만

my_list = [[1, 2], [3, 4], [5, 6]]
answer = []
for element in my_list:
    answer += element

파이썬에서는 for문을 사용하지 않고도 리스트를 이어붙일 수 있다.

• itertools.chain
  

my_list = [[1, 2], [3, 4], [5, 6]]

# 방법 1 - sum 함수
answer = sum(my_list, [])

# 방법 2 - itertools.chain
import itertools
list(itertools.chain.from_iterable(my_list))

# 방법 3 - itertools와 unpacking
import itertools
list(itertools.chain(*my_list))

# 방법 4 - list comprehension 이용
[element for array in my_list for element in array]

# 방법 5 - reduce 함수 이용 1
from functools import reduce
list(reduce(lambda x, y: x+y, my_list))

# 방법 6 - reduce 함수 이용 2
from functools import reduce
import operator
list(reduce(operator.add, my_list))

각 원소의 길이가 동일한 경우라면 numpy의 flatten을 이용할 수도 있다.

# 방법 7 - numpy 라이브러리의 flatten 이용
import numpy as np
np.array(my_list).flatten().tolist()