[프로그래머스] n^2 배열 자르기 - 파이썬(Python3)

문제 링크

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

예시를 보고 max(i, j)+1 이 해당 인덱스에 들어가면 된다고 생각했다.

그렇지만 이중 for문으로 인해 몇몇 케이스에서 시간 초과가 발생했다.. 

 

def solution(n, left, right):
    answer=[]
    graph = [ [0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            graph[i][j]=max(i,j)+1
                    
    for i in graph:
        for j in i:
            answer.append(j)
    
    return answer[left:right+1]

 

풀이 2

검색 결과 사각형의 원리를 이용하면 된다는 것을 알게 되었다.

위치값에서 n을 나눠준 나머지와 몫 중 큰 값을 선택하고 +1을 해주면 된다!

 

정답 코드

def solution(n, left, right):
    answer = []

    for i in range(left, right + 1):
        answer.append(max(i // n, i % n) + 1)

    return answer