[프로그래머스] Lv2 - n^2 배열 자르기

문제

프로그래머스 월간 코드 챌린지 시즌3

• Lv 2. n^2 배열 자르기 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/87390

코드 구현

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

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

    # left부터 right까지 판단
    # 0,2 -> 1,0 -> 1,1 -> 1,2
    # n = 3
    # 2//3 = 0...2 , 3//3 = 1...0, 4//3 = 1...1, 5//3 = 1...2

    return answer

풀이

• 처음에는 무조건 시간초과가 날 것 같았지만 제대로 된 원리를 파악하기 위해 2중 for문으로 짰다.

  def solution(n, left, right):
      answer = []
  
      # 1) n*n 배열 만들기
      # 2) i행 i열을 i로 채우기 (i는 1부터 n까지)
      # 3) 행을 잘라서 이어붙이기
      # 4) left:right 까지 슬라이싱
      # -> 백퍼 시간초과 !
  
      dim_n = [[0 for _ in range(n)] for _ in range(n)]
  
      count_index = 0
      for i in range(len(dim_n)):
          for j in range(len(dim_n)):
              dim_n[i][j] = max(i, j) + 1
              answer.append(dim_n[i][j])
  
              if (count_index == right):
                  answer = answer[left:right + 1]
                  break
  
              count_index += 1
  
      return answer

• 이 코드를 짜면서 알아낸 수식 - 1
  • n * n 배열에서 (i, j) 위치의 값은 둘 중 큰 값에 +1을 한 것과 같다.
  • 따라서 dim_n[i][j] = max(i, j) + 1
• 그러나 시간 초과를 해결하기 위해서는 left 인덱스부터 right 인덱스까지의 값만을 구해야한다. 나머지 값은 구해봤자 비효율적임!
• 그러다 발견한 또 다른 수식 - 2
  - left // n 의 값이 정답의 첫번째 값 인덱스 (i, j) 중 i의 값이고, left % n 의 값이 j의 값이다.
  ex) 입출력 예 1번
  

    n = 3, left = 2, right = 5, answer = [3,2,2,3]
    
    # 3 * 3 배열
    dim_n = [[1,2,3], [2,2,3], [3,3,3]]
    
    # 잘라서 이어붙인 뒤 (i, j) 인덱스를 나열해보면,
      1     2     3     2     2     3     3     3     3
    (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)
    
    # left부터 right까지의 (i, j) 인덱스 값
      3     2     2     3
    (0,2) (1,0) (1,1) (1,2)
    
    # left // n
    2 // 3 = 0
    2 % 3 = 2
    
    # >>> left부터 시작하는 (0, 2) 인덱스가 (left // n, left % n) 부터 시작되는걸 확인!

• 따라서 right를 만날때까지 left의 값을 하나씩 늘려가며 몫과 나머지로 (i, j) 좌표를 구하고
• max(i, j)+1 수식으로 해당 인덱스에 존재하는 값을 구한다면 해결 완료

시간초과 해결 ~!