[프로그래머스] LV.2 n^2 배열 자르기(python)

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

문제 설명

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

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 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

문제 해결

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

 

문제 풀이 설명

1. 첫 번째 풀이

def solution(n, left, right):
    answer = [[0 for _ in range(n)] for _ in range(n)]
    result = []
    for i in range(n):
        l, r = 0, i
        while(l < r):
            answer[l][r] = i+1
            l += 1
        l, r = i, 0
        while(l >= r): # =기호를 빼면 [i][i] 값이 0 이 들어감
            answer[l][r] = i+1
            r += 1
            
    for i in range(len(answer)):
        for j in range(len(answer[i])):
            result.append(answer[i][j])
    return result[left:right+1]

먼저 혹시나 하는 마음에 모든 배열의 값을 구하는 코드를 작성했다.

이후에 이것보다 나은 코드를 작성하긴 하지만 기본 개념은 똑같았다.

첫 번째 풀이 코드에서는 while문을 사용해 복잡하게 2차원 리스트를 구성하지만

간단히 코딩하자면 l과 r의 인덱스 중 최댓값 + 1이 들어가면 된다. 예를 들어 answer[10][12]에는 무슨 값이 들어가야 할까?

바로 max(10, 12) + 1 인 13이 들어가면 된다.(참쉽죠?)

하지만 모든 배열을 구하다 보니 O(n^2)의 시간복잡도가 소요되면서 시간초과로 문제를 해결하지 못했다...

 

2. 두 번째 풀이

어떻게든 시간복잡도를 줄여야 한다고 생각하니까 결국 left와 right 사이에 있는 값만 구하면 안될까? 라는 생각이 들었다.

지금처럼 0 ~ n^2 까지 구하는 것보다 단순히 구해야 하는 부분만 구하면 시간복잡도가 줄것이라고 생각했다.

1) left와 right + 1의 범위까지만 리스트의 값을 구한다.

2) 일차원 리스트와 각 (i, j)와의 관계를 구한다. 아래는 예시의 인덱스와 각 (i, j)를 보여준다.

index0(0,0)

index1(0,1)

index2(0,2)

index3(1,0)

index4(1,1)

index5(1,2)

index6(2,0)

index7(2,1)

index8(2,2)

3) index 5를 봤을 때, 각 i와 j는 1과 2로 (1, 2)로 표현되고 있다. 여기서 i는 index // n, j는 index % n 과 같다.(예시에서는 n은 3이다.)

따라서 5 // 3 ==> 1, 5 % 3 ==> 2 로 i와 j가 표현된다. 그리고 몫과 나머지, 즉 i와 j 중 큰 값이 해당 index의 값이 된다.

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 을 한 결과가 left와 right + 1 까지의 일차원 리스트가 된다.

4) 해당 로직을 코드로 구현하고, 둘 중에 큰 값을 찾아서 +1 해준 값이 해당 index의 값이 된다.

5) 처음부터 left ~ right + 1까지의 리스트를 구했기 때문에, 바로 return 해주면 된다.