Lv2. n^2 배열 자르기

문제 보기 : n^2 배열 자르기

프로그래머스

---

문제

• 정답률 : 66%

 

 

 

---

작성 코드

##1
def solution(n, left, right):
    ans = [] ; answer = []
    for nn in range(1,n+1):
        for i in range(nn):
            if i == nn-1:
                ans.append([nn]*nn) #[[1,2][2,2]]
            else:
                ans[i].append(nn)
    for ls in ans:
        answer += ls
    answer = answer[left:right+1]
    return answer

---

풀이

처음 알고리즘은 이렇게 짰다.

nn번째 시행마다 ans에 저장된 리스트에 nn을 더하고 맨 마지막 리스트엔 [nn]*nn인 리스트를 추가했다.
그리고 answer 리스트에 ans의 작은 리스트를 모두 더하고 left부터 right index까지를 출력한다.
근데 이렇게 알고리즘을 짰을 땐 시간초과와 메모리초과가 났음,,
그럴만도 한게 작은 리스트 전부 만들어야하니까..

그래서 다시 만든 코드는 이렇다.

##2
def solution(n, left, right):
    answer = []
    for i in range(left,right+1):
        x = (i//n)+1
        y = (i%n)+1
        k = max(x,y)
        answer.append(k)
    return answer

​이 알고리즘은 아래를 바탕으로 만들었다.

3x3 행렬로 보자면

(1,1) = 1 (1,2) = 2 (1,3) = 3
(2,1) = 2 (2,2) = 2 (2,3) = 3
(3,1) = 3 (3,2) = 3 (3,3) = 3

이렇게 나타날 수 있고 left=2, right=5이면 [3,2,2,3]을 출력해야하는데

여기에 속하는 (1,3), (2,1), (2,2), (2,3)은 ((left//n)+1, (left%n)+1)로 나타낼 수 있으며

이 두개의 값 중 큰 값이 출력 리스트에 입력해야하는 값이다.