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

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

 

문제

정수 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 함수를 완성해주세요.

입출력

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

제한사항에 대해 보고싶으면 눌러주세요

제한사항

$1 ≤ n ≤ 10^7$
$0 ≤ left ≤ right < n^2$
$right - left < 10^5$

풀이방법

첫번째 풀이 방법

일단, 처음으로 제한사항에서 n이 $10^7$인 것을 보고서, 시간복잡도 문제가 무조건 생길것이라고 판단하였다. 

이러한 형식의 배열을 만들고 펼치는 과정에서 시간초과가 발생할 것이라고 생각했다.

바로 이 과정을 만드는 방법에 대해 고민을 하기 시작했다. 그래서 배열을 펼치는 방식 구현을 생각했다. 

 

인덱스	0	1	2	3	4
숫자	1	2	3	2	2
몫, 나머지	0, 1	0, 2	1, 0	1, 1	1, 2

위와 같은 형식일 때, 몫과 나머지를 이용하는 것을 깨닫고 다음과 같은 형식으로 변환했다.

인덱스	0	1	2	3	4
숫자	1	2	3	2	2
변환한 몫, 나머지	1, 1	1, 2	1, 3	2, 1	2, 2

변환을 진행하고 몫과 나머지 중에서 큰 값을 반환하도록 했다. 다음과 같은 방식으로 해결했다.

코드

def cal_ans(n, idx):
    q, m = idx // n + 1, idx % n 
    
    if m == 0: m += n; q -= 1
    
    if q > m:
        return q
    else:
        return m


def solution(n, left, right):
    answer = []
    for idx in range(left, right+1):
        answer.append(cal_ans(n,idx + 1))
    return answer


if __name__ == "__main__":
    print(solution(4,7,14))

두번째 풀이 방법

단순히 몫과 나머지 중에서 큰 값 + 1을 하면 된다. 여기서 이 것을 깨닫고 좀 현타가 왔다.

코드

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