[프로그래머스] n^2 배열 자르기

 

❎  첫번째 풀이

import itertools

def solution(n, left, right):
    n_list=[[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(0,n):
        for j in range(0,i+1):
            n_list[i][j]=i+1
            n_list[j][i]=i+1
    
    flatten_list=list(itertools.chain(*n_list))
    
    
    return flatten_list[left:right+1]

정직하게 정사각형 이중 배열을 생성하고, flatten 해주고, slice하는 방식

👉🏻 역시나, 시간 초과 발생 

 

 

 

✅  정답 풀이

def solution(n, left, right):
    answer=[]
    
    for x in range(left,right+1):
        a=x//n
        b=x%n
        answer.append(max(a,b)+1)
        
    return answer

 

정직하게 풀이해보니 역시나 안되서, 다른 패턴을 찾아보았지만 그것 또한 2중 for문이라 어차피 같은 시간복잡도였다.

하지만 또 다른 패턴이 숨겨져 있었다.

 

예를 들어 list[7]=list[1][3]과 같다.

👉🏻 row=몫, col=나머지와 같은 인덱스를 가지고 있다.

 

 

list[1][3]=4

list[3][1]=4

👉🏻 array[i][j]의 값은 max(i,j) + 1 이다

 

---

 

그냥 단순 구현문제인줄 알았는데, 패턴찾기 문제였다.

😣 역시 패턴찾기는 어렵당...