[programmers] n^2 배열 자르기

프로그래머스 Lv.2 N^2배열 자르기

문제 분석

이 경우 답은 [4,3,3,3,4,4,4,4] 가 되는 것이다.

첫 번째 코드

def solution(n, left, right):
    arr = [[0 for i in range(0,n)] for j in range(0,n)]
 
    for i in range(0,n):
        for j in range(0,n):
            arr[i][j] = max(i+1,j+1)
        
    newarr = []
    for i in arr:
        newarr += i

    return newarr[left:right+1]

아이디어

1. n by n matrix를 만듬
2. 각 index에 값을 채워넣음 (i,j)좌표의 값은 i,j중 큰 값임
3. newarr을 선언해서 행끼리 더한 배열을 만듬
4. 지시문대로 index를 잘라 넣음

논리 자체가 틀리지는 않았다.
하지만 효율성 테스트를 통과하지 못한다.

arr = [[0 for i in range(0,n)] for j in range(0,n)]

이거만 돌려도 이미 time out이 난다. 다른 방법을 찾아야 한다.

새 아이디어

이번에는 정답에 해당하는 문자열만 정답에 바로 추가해본다.

두 번째 코드

def solution(n, left, right):
    arr = []
    count = 0
    for i in range(0,n):
        for j in range(0,n):
            count += 1
            if count > left and count <= right + 1:
                arr.append(max(i+1,j+1))
    return arr

테스트 1 〉	통과 (23.69ms, 16MB)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	통과 (0.70ms, 9.97MB)
테스트 5 〉	통과 (0.52ms, 10.1MB)
테스트 6 〉	통과 (68.69ms, 18.4MB)

이번에도 역시 안된다. for문을 사용하면 안 되는 것 같다.

또 새 아이디어

이번에는 수학적으로 시작점과 끝점의 좌표를 구한다
1. 시작점은 (left/n)+1, (left%n)+1 임.
2. 끝점은 (right/n)+1, (right%n)+1 임.
3. while문을 돌려서 좌표를 탐색하며 두 좌표 중 큰 값을 추가.
    3-1) y좌표+1이 n을 초과할 경우에는 y = 1, x += 1
    3-2) 그렇지 않으면 y += 1
    3-3) 끝점 좌표에 도착하면 끝점에 대해 추가하고 break
좋다. 바로 구현하자.

세 번째 코드

def solution(n, left, right):
    arr = []
    x1,y1 = int((left-left%n)/n)+1,left%n+1
    x2,y2 = int((right-right%n)/n)+1,right%n+1
 
    while True:
        arr.append(max(x1,y1))
        if y1 + 1 > n:
            y1 = 1
            x1 += 1
        else:
            y1 += 1
      
        if x1 == x2 and y1 == y2:
            arr.append(max(x2,y2))
            break
   
    return arr

느낌이 좋다...!

역시 될것 같았다 ㅎㅎ
이것도 DP문제인건가?