[Programmers][Python] Lv.2 n² 배열 자르기

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: Lv.2 
• 문제 유형: 구현
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

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

프로그래머스

 

 

[코드]

시간초과 발생한 코드 / 시간복잡도 O(n²)

1. 2차원 배열 생성 및 채우기:
   • n x n 크기의 배열 생성: O(n²)
   • 각 행(n)에 대해 최대 n번의 연산: O(n²)
2. 1차원 배열로 변환:
   • 모든 원소를 순회: O(n²)
3. 슬라이싱:
   • right - left + 1 개의 원소 복사: O(right - left)

총 시간복잡도: O(n²)

def solution(n, left, right):

    # 1. i행 i열까지 i로 2차원 배열을 채운다.
    arr = [[0] * n for _ in range(n)]
    for i in range(n):
        # i행 i열까지 i+1로 채움
        for j in range(i+1):
            arr[i][j] = i+1

        # 나머지는 마지막 열까지 i+1 다음 숫자(i+2)로 채움
        for j in range(i+1, n):
            arr[i][j] = j+1

    # 2. 행을 잘라서 모두 이어 붙인 새로운 1차원 배열 생성
    arr1 = []
    for i in range(len(arr)):
        for j in range(len(arr[i])):
            arr1.append(arr[i][j])

    # 3. arr[left, right+1] 까지만 출력
    return arr1[left: right+1]

 

 

수정한 코드 / 총 시간복잡도: O(right-left)

def solution(n, left, right):
    answer = []
    for i in range(left, right + 1):
        row = i // n  # 행 번호
        col = i % n  # 열 번호
        answer.append(max(row, col) + 1)
    return answer

 

코드 설명

2차원 배열:
[1, 2, 3, 4]      # 0행
[2, 2, 3, 4]      # 1행
[3, 3, 3, 4]      # 2행
[4, 4, 4, 4]      # 3행

1차원으로 변환:
[1,2,3,4, 2,2,3,4, 3,3,3,4, 4,4,4,4]
 0 1 2 3  4 5 6 7  8 9...

 

예를 들어 1차원 인덱스 6의 경우:

• row = 6 // 4 = 1 (1행)
• col = 6 % 4 = 2 (2열)
• 값은 max(1, 2) + 1 = 3

원래 규칙:

1. i행 i열까지는 i+1로 채움
2. 그 이후는 열 번호+1로 채움

이 규칙은 결국 각 위치에서 max(행 번호, 열 번호) + 1과 동일