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

프로그래머스를 단순히 풀어보고 나름대로 정리해본 것 입니다

최근에 프로그래머스 월간 코드 챌린지에서도 풀어봤던 문제인데
이렇게 바로 코딩테스트 연습에 뜨다니 정말 빠르다 😮

지난번에는 수행시간이 O(N^2) 나오도록 풀었는데 이번에는 O(N)정도
걸리도록 해보았다 !

⚾ 문제 링크

N^2 배열 자르기

🥎 문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

✨제한사항

1 ≤ n ≤ 107
0 ≤ left ≤ right < n2
right - left < 105

✨ 입출력 예

n left right result
3 2 5 [3,2,2,3]
4 7 14 [4,3,3,3,4,4,4,4]

✨ 입출력 예 1번

🏀 풀이

먼저 index를 확인한다 입출력 1번을 보면,

(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)

다음과 같이 구성되어있다.
1,2,3 이 찍히는 곳의 규칙을 살펴 보면
(0,0) 이면 1, 인덱스에 1이 한개라도 들어가면 2,
인덱스에 2가 하나라도 들어간 곳은 3이다.

그래서 처음 풀이했을땐 2차원 배열로 3*3 행렬을 만들어주고
-> 9 x 1행렬을 만들어주었다.

근데 열이 1인 행렬로 생각해본다면

0 (0,0)	1 (0,1)	2 (0,2)	3 (1,0)	4 (1,1)	5 (1,2)	6 (2,0)	7 (2,1)	8 (2,2)

이런식으로 볼수 있다.
이는 앞의 index 8번을 본다면, 8 ( 8//3, 8% 3)( 몫, 나머지)로 확인할 수 있다. 그리고 몫과 나머지중 가장 큰값에 따라서 숫자가 들어간다

0 (0,0)	1 (0,1)	2 (0,2)	1 (1,0)	1 (1,1)	2 (1,2)	2 (2,0)	2 (2,1)	2 (2,2)

이거에 +1을 한것이 답이 된다 !

그래서 초기의 풀이는

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

이렇게 풀었는데 테스트 케이스에서 시간초과가 발생한다 !
n*n을 지나가기 때문에 오래걸리는 것이다.

🏐 최종 풀이

def solution(n, left, right):
    answer = []
    for i in range(left,right+1):
        a = i//n # 몫
        b = i%n #나머지 
        if a<b: a,b =b,a 큰거 구하기 
        answer.append(a+1)
    
    return answer