99클럽 코테 스터디 1일차 TIL - n^2 배열 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/87390?language=python3

오늘의 학습 키워드

• 시간복잡도

회고

2차원 배열을 이중 포문을 돌아서 만들었더니, 시간복잡도가 O($N^2$)이라 시간초과가 났다.
문제 조건에서 n의 범위가 $1 ≤ n ≤ 10^7$이라 상한이 $10^{14}$이다.
1초에 보통 1억번 연산을 한다고 가정했을 때, $10^6$ 초가 걸리는 것이다. 당연히 시간초과가 날 수 밖에 없었다.

• 처음 작성한 코드

  def solution(n, left, right):
    answer = []
    arr2d = [[0 for _ in range(n)] for _ in range(n)] # 2차원 배열
    for i in range(n):
        for j in range(n):
            if j <= i:
                arr2d[i][j] = i + 1
            else:
                arr2d[i][j] = j + 1
    arr1d = [e for row in arr2d for e in row]
    answer = arr1d[left : right+1]
    return answer

좀 더 효율적으로 문제를 해결하기 위해, 2차원 배열을 만들지 않고 규칙을 찾아야만 했다.
고민 끝에 발견한 규칙은 다음과 같다.

• 1차원 배열에서 각 인덱스 i의 값은 n으로 나눈 수(i // n)와 n으로 나누었을 때 나머지(i % n) 중 큰 수

이는 시간복잡도가 O(N)으로 모든 테스트케이스를 통과했다.

• 제출한 코드

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

알고리즘 문제를 풀기 전에 설계를 먼저 하는 습관을 들여야 한다.
개발에도 요구 분석(or 기획) -> 설계 -> 개발 -> ... 의 과정이 있듯이 문제에 주어진 시간과 메모리 제한 조건을 보고, 어떤 자료구조를 써야 할지, 어떤 알고리즘을 써야 할지 그 범위를 제한할 수 있다.
바로 코드를 작성하려고 하지 말고, 최소 5분 ~ 10분 정도는 문제를 읽고, 이해하고, 설계를 해보자.