[Algorithm] Programmers : n^2 배열 자르기 by Python

[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/87390

코딩테스트 연습 - n^2 배열 자르기

 

📌 문제 설명

정수 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

---

💡 문제 풀이

문제설명이 짧은 만큼 단순한 내용의 문제이지만, 문제를 통과를 하기 위해서는 효율성을 만족시켜야 한다.

 

첫 번째 시도는, 문제에서 주어진 "제한사항"을 간과하고 단순히 구현을 하였다.

1. 주어진 n값을 기준으로 nxn 행렬을 만든다.

2. 규칙에 맞게 행렬에 숫자를 채운다.

3. 2차 행렬을 1차로 변환한다.

4. 인덱스를 이용하여 원하는 값을 반환한다.

 

코드는 다음과 같다.

def step1(n, matrix):
    num = n+1
    pos = n
    matrix[n][n] = num
    while n:
        matrix[n-1][pos] = num
        matrix[pos][n-1] = num
        n -= 1
    return matrix

def step2(matrix):
    answer = []
    for li in matrix:
        answer += li
    return answer

def solution(n, left, right):
    matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        matrix = step1(i, matrix)
    answer = step2(matrix)
    return answer[left:right+1]

하지만 결과는 [시간초과]로 인하여 통과되지 않았다.

 

---

 

두 번째 시도는, 첫 번째 과정에서 불필요한 작업이 너무 많아서 [시간초과]가 발생한다고 생각하여

알고리즘을 개선하였다. 

 

코드는 다음과 같다.

def solution(n, left, right):
    answer, num = [], 1
    for _ in range(n):
        length = n
        for i in range(num):
            answer.append(num)
            length -= 1
        last = num
        for i in range(length):
            last += 1
            answer.append(last)
        num += 1
    return answer[left:right+1]

하지만, 결과는 역시나 시간초과...

 

---

그제서야 제한사항에 n의 범위가 상당히 크다는 것을 느꼈고, nxn의 행렬을 만든 후 인덱스를 통해 반환하는 것이 아닌

규칙을 이용하여 원하는 값만 바로 반환해야함을 깨달았다.

행렬의 대각선을 기준으로 값이 변한다는 규칙을 파악하면, 굉장히 단순한 문제였다...

 

1. 반환해야하는 인덱스의 범위(left ~ right)를, 반복문을 이용하여 각각 n으로 나눈 몫, 나머지를 구한다.

2. 이후 몫이 나머지보다 크거나 같은경우 몫을 반환 / 몫이 나머지보다 작은 경우 나머지를 반환하면 된다.

 

코드는 다음과 같다.

def solution(n, left, right):
    answer = []
    for num in range(int(left), int(right+1)):
        share, rest = (num // n)+1, (num % n)
        if share > rest:
            answer.append(share)
        else:
            answer.append(rest+1)
    return answer

※ 문제를 제출했을 때, 2개의 테스트케이스에서 [런타임]에러가 났었는데, '질문하기'에서 확인한 결과 left, right에 int형이 아닌 다른 경우가 존재하는 것 같다... int형으로 변환시켜주면 통과된다.