12월 4주차 코딩 테스트

1. 원 그리기

풀이

이 문제는 원의 중심좌표와 탐색하고자하는 픽셀좌표와의 거리를 구한다.

만약 원의 반지름보다거리가 작거나 같으면 원을 그리는데 포함되는 픽셀이고 원의 반지름 보다 크다면 원을 그리는데 포함되지 않는다.

피타고라스의 정의를 사용한다.

문제에서 픽셀영역(네모박스)에서의 중심좌표가 픽셀의 좌표가 된다.(아래 그림의 보라색 삼각형)

문제의 특성상 픽셀의 일부가 조금이라도 닿는다면 원에 포함되야 한다. 따라서 0.5를 x, y좌표에 빼줌으로써 그 값이 c’이 c보다 큰지 작은지를 판단하는 것이다.

x, y는 탐색하고자하는 좌표. cx, cy는 원의 중심좌표라고 할때 수식은 아래와 같다.

a' = | x - cx | - 0.5
b' = | y - cy | - 0.5

a^{'2} + b^{'2} = c^{'2} \leq r^2

조건이 만족하면 해당 픽셀에 색깔을 칠하고 그렇지 않으면 칠하지 않는다.

인덱스가 높은 원부터 렌더링 하기

효율적으로 동작하기 위해 문제에서 shapes는 인덱스가 낮은원부터 렌더링하다가 인덱스가 높은 원이 색을 덮어 씌운다. 따라서 shapes를 거꾸로 탐색해 인덱스 높은원이 렌더링을 하게되면 다른 원을 렌더링하지 않고 바로 다음 좌표 탐색으로 넘어간다.

x, y좌표 반전

문제에서 x, y좌표값은 img[y][x]에 저장된다고 하였다.

예를들어 (1, 0)을 탐색하고 싶다면 (0, 1)을 탐색해야 한다는 뜻이다. → img[1][0] 에 넣어주기 때문

img[1][0] = (0, 1)좌표

img[2][0] = (0, 2)좌표

img[0][2] = (2, 0)좌표

따라서 is_inside함수에서 픽셀값을 반전시켜서 넣어준다. 그렇게되면 y = 0, x = 1일때

img[y][x] = img[0][1] = is_inside(1, 0)이 된다.

전체 코드는 아래와 같다.

def solution(M, N, shapes, colors):
    img = [[0 for _ in range(N)] for _ in range(M)] # cols = N rows = M
    
    for y in range(M): 
        for x in range(N):
            for i in range(len(shapes)-1, -1, -1):
                cx, cy, r = shapes[i]
                if is_inside(x, y, cx, cy, r):
                    img[y][x] = colors[i]
                    break
    
    return img


# 픽셀 사각형 중 원의 중심에서 가장 가까운 지점이 원 내부일 경우 내부로 판단
def is_inside(x, y, cx, cy, r):
    d2 = 0
    if x == cx:
        d2 = (abs(y - cy) - 0.5) ** 2
    elif y == cy:
        d2 = (abs(x - cx) - 0.5) ** 2
    else:
        d2 = (abs(x - cx) - 0.5) ** 2 + (abs(y - cy) - 0.5) ** 2
    
    return d2 < r**2

TestCase

# TestCase 1
입력값 〉 10, 15, [[5, 4, 3], [8, 5, 4]], [50, 200]
기댓값 〉 
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 50, 50, 50, 200, 200, 200, 200, 200, 0, 0, 0, 0], 
[0, 0, 50, 50, 50, 200, 200, 200, 200, 200, 200, 200, 0, 0, 0], 
[0, 0, 50, 50, 200, 200, 200, 200, 200, 200, 200, 200, 200, 0, 0],
[0, 0, 50, 50, 200, 200, 200, 200, 200, 200, 200, 200, 200, 0, 0],
[0, 0, 50, 50, 200, 200, 200, 200, 200, 200, 200, 200, 200, 0, 0], 
[0, 0, 50, 50, 200, 200, 200, 200, 200, 200, 200, 200, 200, 0, 0], 
[0, 0, 0, 50, 200, 200, 200, 200, 200, 200, 200, 200, 200, 0, 0], 
[0, 0, 0, 0, 0, 200, 200, 200, 200, 200, 200, 200, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 200, 200, 200, 200, 200, 0, 0, 0, 0]]

# TestCase 2
입력값 〉 20, 20, [[3, 3, 5], [14, 3, 9], [19, 20, 5]], [100, 210, 70]
기댓값 〉
[[100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[100, 100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[0, 100, 100, 100, 100, 100, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[0, 0, 0, 0, 0, 0, 0, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[0, 0, 0, 0, 0, 0, 0, 0, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 210, 210, 210, 210, 210, 210, 210, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 70, 70, 70],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 70, 70, 70, 70, 70],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 70, 70, 70, 70, 70],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 70, 70, 70, 70, 70, 70],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 70, 70, 70, 70, 70, 70]]

5. 배열의 최솟값

풀이

처음에는 문제를 읽고 이해가 잘 안 되었다.

추가 설명을 하자면 n개를 제거하는 것은 순서 상관없이 아무거나 n개를 제거할 수 있다.

그리고 n개로 나누어 합의 차를 계산하는 것은 연속된 n개여야 한다는 것임으로 이는 정렬을 해서는 안 된다.

nums = [10, 4, 9, 6, 8, 1, 9, 4, 10, 4, 5, 8] 예시의 경우 총 12개의 배열임으로 n = 4가 된다.

4개를 제거할 수 있음으로 nums[0](10), nums[2](9), nums[7](4), nums[9](4) 를 제거하면 된다.

nums = [~~10~~, 4, ~~9~~, 6, 8, 1, 9, 4, 10, ~~4~~, 5, 8]

그러면 앞쪽 4개는 4 + 6 + 8 + 1 = 19가 되고 뒤쪽 4개는 9 + 10 + 5 + 8 = 32 가 됨으로 19 - 32 =-13 이 된다.

전체코드는 아래와 같다.

def solution(nums):
	N = len(nums)
	del_count = N // 3
	left_count = N - del_count
	min_total = float('inf')
 
	def dfs(start, path):
		nonlocal min_total
		if len(path) == left_count:
			total = sum(path[:del_count]) - sum(path[del_count:])
			min_total = min(total, min_total)

		if len(path) > left_count:
			return
  
		for i in range(start, N):
			dfs(i+1, path+[nums[i]])
	
	dfs(0, [])
	return min_total

위 처럼 모든 경우에 대해서 탐색하게 했더니 기본적인 테스트 케이스는 통과하지만 그외는 전부 시간초과가 발생한다.

이를 최적화 해보자.

예를들어 길이가 3n 배열이 있다면 n개를 제외하고 총 2n개의 배열에서 앞쪽 n개의 배열의 합과 뒤쪽 n개의 배열의 차가 가장 작아야 한다. 즉 앞쪽 n개의 배열의 합은 되도록 작아야 하고 뒤쪽 n개의 배열의 합은 되도록 커야 한다.

예를들어 nums = [7, 9, 1, 5, 8, 3] 이라 해보자.

left는 nums의 갯수 만큼 0으로 초기화해준다: left = [0, 0, 0, 0, 0, 0]

right는 nums의 갯수 만큼 0으로 초기화해준다: right = [0, 0, 0, 0, 0, 0]

left 구하기

left초기화를 위해 0부터 n-1까지의 합을 구하고 left[n-1]에 저장해준다.

left[1] = 7 + 9 = 16 = [0, 16, 0, 0, 0, 0]

그리고 2(n) 부터 3(2n - 1)까지 하나씩 최대값을 힙큐로 뽑고 그 값을 빼줌으로서 최솟값을 만들어나간다.

left[2]: nums의 0 ~ 2번 인덱스까지의 최솟값을 보장 → 0 ~ 2번중에서 가장 작은 값을 빼고 2번인덱스를 더한다. → 7 + 9 + 1 - 9 = 8
left[3]: nums의 0 ~3번 인덱스까지의 최솟값을 보장 → 0 ~ 3번중에서 가장 작은 값을 빼고 3번인덱스를 더한다. → 8 + 5 - 7 = 6

left = [0, 16, 8, 6, 0, 0]

right 구하기

right 초기화를 위해 2n부터 3n까지의 합을 구하고 right[2n]에 저장해둔다.

right[4] = 8 + 3 = 11 = [0, 0, 0, 0, 11, 0]

그리고 거꾸로 3(2n-1) 부터 2(n)까지 하나씩 힙큐로 최솟값을 뽑고 그 값을 빼줌으로서 최대값을 만들어나간다.

right[3]: nums의 3 ~ 5번 인덱스까지의 최대값 보장 → 3 ~ 5번중에서 가장 작은 값을 빼고 3번인덱스를 더한다. → 8 + 3 + 5 - 3 = 13
right[2]: nums의 2 ~ 5번 인덱스까지의 최대값 보장 → 2 ~ 5번중에서 가장 작은 값을 빼고 2번 인덱스를 더한다. → 13 + 1 -1 = 13

right = [0, 0, 13, 13, 11, 0]

이렇게 만들었으면 이상태에서 left[i]와 right[i + 1]값을 빼주면서 최솟값을 구한다.

전체 코드는 아래와 같다.

import heapq

def solution(nums):
    m = len(nums)
    n = m // 3

    left = [0 for _ in range(m)]
    right = [0 for _ in range(m)]

    left[n-1] = sum(nums[0:n])
    q1 = [-num for num in nums[:n]]
    heapq.heapify(q1)
    for i in range(n, 2*n): # 최소가 되도록
        heapq.heappush(q1, -nums[i])
        v = heapq.heappop(q1)
        left[i] = left[i-1] + nums[i] + v

    right[2*n] = sum(nums[2*n:])
    q2 = nums[2*n:]
    heapq.heapify(q2)
    
    for i in range(2*n-1, n-1, -1): # 최대가 되도록
        heapq.heappush(q2, nums[i])
        v = heapq.heappop(q2)
        right[i] = right[i+1] + nums[i] - v
    
    res = float('inf')
    for i in range(n-1, 2*n):
        res = min(res, left[i] - right[i+1])
    return res

TestCase

# TestCase 1
입력값 〉 [7, 9, 1, 5, 8, 3]
기댓값 〉 -5

# TestCase 2
입력값 〉 [10, 4, 9, 6, 8, 1, 9, 4, 10, 4, 5, 8]
기댓값 〉 -13

출처

해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.

12월 4주차 코딩 테스트

목차

1. 원 그리기

풀이

TestCase

5. 배열의 최솟값

풀이

TestCase

출처

Comment