[2/22] 기출문제 풀이

👉 사용 언어 : PYTHON3

n^2 배열 자르기

✅ Solution

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

def solution(n, left, right):
    answer = []
    temp = [num for num in range(1, n+1)]
    for i in temp:
        answer += [i] * i
        answer.extend(temp[i:])
    return answer[left:right+1]

 

: 위의 두가지 풀이 방법은 시간 초과 발생

👉 n의 범위가 최대 10^7이고 문제에서 left와 right를 제시해줬기 때문에 left 이전과 right 이후의 의미없는 값들은 아예 만들지 않고 스킵하는 방식으로 코드를 짜야 한다.

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

 

👉 문제 설명 및 제한 사항

• 매개변수 : 정수 n, left, right
  • 1 ≤ n ≤ 107
  • 0 ≤ left ≤ right < n2
  • right - left < 105
• 리턴값 : 아래 과정대로 만들어진 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] 만 남기고 나머지는 지운다.
• 문제 이해를 위한 애니메이션 > 문제 링크 참고 https://school.programmers.co.kr/learn/courses/30/lessons/87390

 

👉 아이디어

• 첫 번째 풀이
  • 중첩 for문 을 돌려서 행과 열중에 max값을 정답 배열에 추가한다.
  • 이 때, index+1 = 순서이므로 max+1을 해서 추가해야함을 유의해야 한다.
  • 문자열 슬라이싱 을 사용하여 정답 배열[left : right+1] 을 리턴한다.
• 두 번째 풀이
  • 1, 2, ..., n 으로 구성된 temp 배열을 생성한다.
  • 예시를 보면 [[1, 2, 3, ..., n], [2, 2, 3, ..., n], [3, 3, 3, 4, ..., n], ..., [n, n, n, ..., n]] 형태의 2차원 배열 이 만들어진다.
  • 따라서, 1부터 n까지 for문 을 돌려서 i * i와 i+1, ..., n을 정답 배열에 추가한다.
  • 문자열 슬라이싱 을 사용하여 정답 배열 [left : right+1] 을 리턴한다.
• 최종 풀이 답안
  • 인덱스의 몫과 나머지 를 사용하였다.
  • 배열의 index = y * n + x 이므로
    • x = i % n
    • y = i // n
  • 따라서, left부터 right+1 까지 for문을 돌려 x(= i % n)와 y(= i // n) 중 max값을 정답 배열에 추가한다.
    • 이 때, index+1 = 순서이므로 max+1을 해서 추가해야함을 유의해야 한다.
  • 정답 배열을 그대로 리턴한다.

 

✅ 다른 사람 풀이 참고

 

: 위의 풀이와 유사함.

 

👉 깨달은 것 / 알게된 것

• 입력값의 범위 가 클 경우, 반복문의 range 를 줄이는 쪽 으로 풀이방법을 생각해야 한다.
  • 위의 문제 같은 경우에도 n이 최대 10^7이므로 중첩 for문을 돌리면 O(10^14)로 시간 초과가 발생하며, 테스트를 통과한다해도 매우 비효율적인 코드가 된다.
  • 수식으로 접근❗

행렬의 곱셈

✅ Solution

def solution(arr1, arr2):
    answer = []
    for i in range(len(arr1)):
        temp = []
        for j in range(len(arr2[0])):
            num = 0
            for k in range(len(arr2)):
                num += arr1[i][k]*arr2[k][j]
            temp.append(num)
        answer.append(temp)
    return answer

 

👉 문제 설명 및 제한 사항

< 행렬의 곱셈 과정 >

< 예시 풀이를 통해 규칙을 찾아내기 >

• 매개변수 : 2차원 배열 arr1, arr2
  • 2 <= 행렬 arr1, arr2의 행과 열 길이 <= 100
  • -10 <= 행렬 arr1, arr2의 원소  <= 20
  • 곱할 수 있는 배열만 주어진다.  (arr1 열 길이 == arr2 행 길이 만족)
• 리턴값 : arr1 * arr2 결과값(= 2차원 배열)

👉 아이디어

• 우선, 정답 배열의 크기가 arr1 행 길이 * arr2 열 길이라는 것을 생각하고 풀어야 한다.
• for문 3개 를 중첩해서 돌린다.
  • 가장 안쪽  for문 : k
    • 반복문 범위 : arr1의 열 길이 (= arr2의 행 길이)이므로 len(arr2) 또는 len(arr1[0])❗️
    • 위의 두 번째 그림에서 하나의 num을 만드는 것과 같다.
    • 첫 번째 예제에서는 [[]] 안 각각의 15를 만드는 과정
  • 중간  for문 : j
    • 반복문 범위 : arr1의 행 길이이므로 len(arr2[0])❗️
    • 위의 두 번째 그림에서 하나의 temp 배열(= num 묶음)을 만드는 것과 같다.
    • 첫 번째 예제에서는 [] 안의 [15, 15]를 만드는 과정
  • 가장 바깥쪽  for문 : i
    • 반복문 범위 : 정답 배열의 행 길이 == arr1 행 길이이므로 len(arr1)❗️ 
    • 리턴할 정답 배열(= temp 배열 묶음)을 만드는 과정이다.
    • 첫 번째 예제에서는 [[15, 15], [15, 15], [15, 15]]를 만드는 과정

 

✅ 다른 사람 풀이 참고

import numpy as np
def productMatrix(A, B):
    return (np.matrix(A)*np.matrix(B)).tolist()

def solution(A, B):
    return [[sum(a*b for a, b in zip(A_row,B_col)) for B_col in zip(*B)] for A_row in A]

 

👉 깨달은 것 / 알게된 것

• numpy 모듈을 임포트하여 제공하는 메소드를 사용하여 풀이할 수 있다.
  • .matrix(list) : 배열 > 행렬
  • 행렬끼리의 곱셈 연산 가능
  • 하지만 numpy를 사용할 수 없는 경우도 있으므로 직접 풀이하는 것을 권장한다.
• zip() 메소드를 사용하여 풀이할 수 있다.
  • zip(*B) : 행 > 열로 변환
    • EX :  zip(*[[1,2], [3,4], [5,6]]) > [(1, 3, 5), (2, 4, 6)]
  •  zip(A_row,B_col) 를 사용하여 각 행 * 각 열 값을 리스트로 변환하여 리턴한다.