달팽이 배열로 숫자 채워넣기

1. 문제

 

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

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

 

정수 n이 매개변수로 주어집니다.

 

다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서

 

맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후,

 

첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return하도록 solution함수를 완성하세요.

 

 

2. 제한사항

 

n은 1 이상 1000이하

 

3. 예시

 

 

4. 나의 풀이

 

핵심이라고는 뭐하지만 채워야하는 수가 1부터 어디까지인지 생각을 해보면

 

위에서부터 1줄,2줄,3줄,4줄,...,n줄을 채우니까

 

1부터 n까지의 합 $\frac{n(n+1)}{2}$만큼의 수를 사용해야한다

 

다음 각 줄마다 길이만큼 0을 채운 이중 리스트를 만들도록 한다

 

def solution(n):
    
    answer = []
    
    total_number = n*(n+1)/2
    
    for i in range(1,n+1):
        
        answer.append([0]*i)

 

이제 i=1부터 total_number까지 리스트에 수를 채워넣을려고 하는데

 

먼저 앞줄을 순서대로 1,2,3,4,5,...,n까지 채워넣고자 한다

 

 

answer에서 리스트 하나씩 뽑은다음에

 

answer에 0이 있다면… 그 리스트 길이를 last로 하고

 

range(0,last)까지 돌건데

 

리스트 내의 원소중 0이 있으면 i를 집어넣고 i에 1을 더한다음에 바로 break해서 다음 for문으로 넘어가도록

 

이렇게 하는 이유는 다음 반복문에서도 재활용해서 사용하고자 하는거임

 

while i <= total_number:
    
    for a in answer:
        
        if 0 in a:
            
            last = len(a)
            
            for ind in range(0,last):
                
                if a[ind] == 0:
                
                     a[ind] = i
                     
                     i += 1
                     
                     break

 

다음으로는 마지막 줄을 채워넣을거임

 

 

answer에서 마지막 리스트부터 뽑을거임

 

그 리스트 내에 0이 있다면 그 리스트의 전체 길이를 구한다음에

 

for문을 돌아서 위에서 i에 이어서 0인 부분에 i를 1을 더해가면서 채워넣고

 

for a in answer[::-1]:
    
    if 0 in a:
        
        last = len(a)
        
        for ind in range(last):
            
            if a[ind] == 0:
                
                a[ind] = i
                
                i += 1
                
        break

 

리스트 다 채워넣으면 전체 for문을 break해서 다음으로 넘어가도록

 

 

다음은 각 줄마다 마지막 원소를 올라가면서 순서대로 채워넣을거임

 

for a in answer[::-1]:
    
    if 0 in a:
        
        last = len(a) * (-1)
        
        for ind in range(-1, last, -1):
            
            if a[ind] == 0:
                
                a[ind] = i
                
                i += 1
                
                break

answer의 마지막부터 for문을 돌건데

 

리스트에 0이 있다면 그 리스트 내부를 거꾸로 돌거임

 

거꾸로 도는 방법은 위 그림과 같이 -1부터 last까지 -1을 더해가면서 돈다

 

이 때 리스트 내부에 0이 있는 부분은 바로 i를 채워넣고 1을 더한다음에 for문의 다음 반복으로 넘어가도록

 

이제는 while문을 계속해서 반복하면 된다

 

 

i가 total_number보다 커지면 알아서 while문을 탈출할거임

 

그러면 이제 answer에는 [[1],[2,9],[3,10,8],[4,5,6,7]] 같이 있을거

 

그러면 answer를 전체 한번 돌아서 extend를 이용해 리스트 전체 원소를 순서대로 집어넣으면 끝

 

answer_list = []

for a in answer:
    
    answer_list.extend(a)
    
return answer_list

 

 

5. 다른 풀이

 

30배 빠르게 푼 코드가 있어서 분석을 해보면

 

from itertools import chain

def solution(n):
    
    [row,col,cnt] = [-1,0,1]
    
    board = [[None] * i for i in range(1,n+1)]
    
    for i in range(n):
        
        for _ in range(n-1):
            
            if i % 3 == 0:
                
                row += 1
                
            elif i % 3 == 1:
                
                col += 1
                
            else:
            
                row -= 1
                
                col -= 1
            
            board[row][col] = cnt
            
            cnt += 1
            
    return list(chain(*board))

 

행,열을 이용한것 같네

 

 

n=5일때 예를 들어 3행 1열에는 3이 들어가고 이런거 인듯

 

board 만드는건 내가 했던거랑 비슷하네 근데 여기선 0 대신에 None으로

 

for문을 0부터 n-1까지 먼저 돌건데

 

다음 for문은 0부터 n-i-1까지네

 

i=0이니까 0부터 n-1까지 돌거고 일단 row=0이 되는거고

 

board[0][0] = 1을 넣은다음에 cnt에 1을 더해줘

 

--------------------------------------------------------------------------------------------

 

다음 for문에서 row=1이 되고 board[1][0] = 2를 넣은 다음에 cnt에 2를 더해..

 

그러면 이 for문 돌때는 삼각 배열에서 각 행마다 맨 앞에 있는 0열의 원소를 채워 넣는 과정이네

 

그러면 이 for문 돌때는 삼각 배열에서 각 행마다 맨 앞에 있는 0열의 원소를 채워 넣는 과정이네

 

---------------------------------------------------------------------------------------------------------------

 

그러면 이제 다음 for문에서 i=1이 되는데

 

i=1이면 col에 1을 더하네

 

이전 for문을 다 돌때 row=n-1이거든요

 

그러면 이 for문에서는 마지막 줄의 원소를 1을 더해가며 채워넣을거고

 

그 다음 for문에서 i=2가 되는데

 

내부 for문을 돌때 row에 1을 빼고 col에 1을 빼나가는데

 

그러면 이 for문은 각 행마다 마지막 원소를 채워 넣는 과정이네

 

---------------------------------------------------------------------------------------------------------------

 

결국 전체 알고리즘은 까보면 나랑 동일한데 시간은 30배나 줄였네

 

itertools의 chain함수는 iterator들을 하나로 연결하는 역할을 하는데

 

board가 n=4이면 [[1],[2,9],[3,10,8],[4,5,6,7]] 이렇게 되어 있을텐데

 

*board하면 [1],[2,9],[3,10,8],[4,5,6,7] 이렇게 만들어서 chain에 넘겨주고

 

chain은 각 리스트들을 하나로 연결한 iterator인

 

iterator( 1,2,9,3,10,8,4,5,6,7 ) 이렇게 만들어주는데

 

여기에  list를 씌워서 [1,2,9,3,10,8,4,5,6,7]을 만들어 return함

 

 

6. 되돌아보기

 

시간을 좀 많이 소요하는 코드긴 했는데 예전같았으면 풀지도 못할거

 

어떻게 풀었다는게 실력이 많이 올랐다는거

 

문제 핵심도 나름 잘 파악했구만

 

어려워보였지만 알고리즘은 생각보다 별거 없었다... 그냥 그림 그대로 집어넣는거였음

 

시간을 더 줄이는건 조금 아쉽긴한데

 

열심히해야지

 

itertools도 나름 유용하다는데 잘 기억해두자