나를 잃지 말자

• 문제
  • 2차원 배열이 주어진다. 이 때 이웃한 네개의 영역의 합의 최댓값을 구하시오.
  • 이웃한다란, 위, 아래, 좌, 우로 이동할 수 있음을 가리킨다.
• 해결

import sys

height, width = [int(x) for x in sys.stdin.readline().split()]

mapping = [list(map(int, x.split())) for x in sys.stdin.readlines()]
case_to_sub = {
    0: 2,
    1: 1,
    2: 8,
    3: 4,
    4: 4
}

def case_sub_to_available(case, sub, total_row, total_col):
    if case == 0 and sub == 0:
        return total_row, total_col - 3, 0, 0
    elif case == 0 and sub == 1:
        return total_row - 3, total_col, 0, 0

    elif case == 1 and sub == 0:
        return total_row - 1, total_col - 1, 0, 0

    elif case == 2 and sub == 0:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 1:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 2 and sub == 2:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 3:
        return total_row - 1, total_col - 2, 1, 0

    elif case == 2 and sub == 4:
        return total_row - 2, total_col - 1, 2, 0
    elif case == 2 and sub == 5:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 2 and sub == 6:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 7:
        return total_row - 1, total_col - 2, 0, 0

    elif case == 3 and sub == 0:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 3 and sub == 1:
        return total_row - 1, total_col - 2, 1, 0

    elif case == 3 and sub == 2:
        return total_row - 2, total_col - 1, 1, 0
    elif case == 3 and sub == 3:
        return total_row - 1, total_col - 2, 0, 0

    elif case == 4 and sub == 0:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 4 and sub == 1:
        return total_row - 2, total_col - 1, 1, 0
    elif case == 4 and sub == 2:
        return total_row - 1, total_col - 2, 1, 0
    elif case == 4 and sub == 3:
        return total_row - 2, total_col - 1, 0, 0

def get_val(case, sub, r, c, d):
    if case == 0 and sub == 0:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r][c + 3]
    elif case == 0 and sub == 1:
        return d[r][c] + d[r + 1][c] + d[r + 2][c] + d[r + 3][c]

    elif case == 1 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r][c + 1] + d[r + 1][c + 1]

    elif case == 2 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r + 2][c] + d[r + 2][c + 1]
    elif case == 2 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c]
    elif case == 2 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r + 1][c + 1] + d[r + 2][c + 1]
    elif case == 2 and sub == 3:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r - 1][c + 2]

    elif case == 2 and sub == 4:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r - 2][c + 1]
    elif case == 2 and sub == 5:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c + 2]
    elif case == 2 and sub == 6:
        return d[r][c] + d[r][c + 1] + d[r + 1][c] + d[r + 2][c]
    elif case == 2 and sub == 7:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 1][c + 2]

    elif case == 3 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 2][c + 1]
    elif case == 3 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r - 1][c + 2]
    elif case == 3 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r + 1][c]
    elif case == 3 and sub == 3:
        return d[r][c] + d[r][c + 1] + d[r + 1][c + 1] + d[r + 1][c + 2]

    elif case == 4 and sub == 0:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c + 1]
    elif case == 4 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r + 1][c + 1]
    elif case == 4 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r - 1][c + 1]
    elif case == 4 and sub == 3:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 2][c]

max_ = 0
for case in case_to_sub.keys():
    for sub in range(case_to_sub[case]):
        row_cnt, col_cnt, start_row, start_col = case_sub_to_available(case, sub, height, width)
        for r in range(start_row, start_row + row_cnt, 1):
            for c in range(start_col, start_col + col_cnt, 1):
                val = get_val(case, sub, r, c, mapping)
                if val > max_:
                    max_ = val
print(max_)

• 포인트
  • 테트로미노와 같다.
  • Bruteforce로 해결한다.

• 문제
  • 수열이 주어졌을 때 서로 다른 두 요소의 합의 최댓값을 구하시오. 단, 두 요소는 연속해서는 안된다.
    • 각 요소는 정수이다.
    • 수열의 길이는 최대 1,000,000
  • 예시
    • 1 2 6 7 8 → 6 + 8 =14 가 정답
    • 9 8 7 9 → 9 + 9 = 18 가 정답
• 해설

import sys

numbers = [int(x) for x in sys.stdin.readline().split()]

# 수열의 길이가 3일 때
if len(numbers) == 3:
	print(numbers[0] + numbers[2])

# 수열을 한번 돌면서 top-4 element의 값과 index를 저장한다.
top_four_values = {1:0, 2:0, 3:0, 4:0}
top_four_indexs = {1:0, 2:0, 3:0, 4:0}
for idx, val in enumerate(numbers):
	# 현재까지 1등보다 컸다면
	if val > top_four_values[1]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = top_four_values[2]
		top_four_indexs[3] = top_four_indexs[2]
		top_four_values[2] = top_four_values[1]
		top_four_indexs[2] = top_four_indexs[1]
		top_four_values[1] = val
		top_four_indexs[1] = idx
		
	# 현재까지 1등보다는 작지만 2등보다 컸다면
	elif val > top_four_values[2]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = top_four_values[2]
		top_four_indexs[3] = top_four_indexs[2]
		top_four_values[2] = val
		top_four_indexs[2] = idx

	# 현재까지 2등보다는 작지만 3등보다 컸다면
	elif val > top_four_values[3]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = val
		top_four_indexs[3] = idx

	# 현재까지 3등보다 작지만 4등보다 컸다면
	elif val > top_four_values[4]:
		top_four_values[4] = val
		top_four_indexs[4] = idx

# 네 개의 indexs와 values로 정답찾기
maximum = 0
for i in range(1, 4, 1):
	for j in range(2, 5, 1):
		if abs(top_four_indexs[i] - top_four_indexs[j]) > 1:
			if maximum < (top_four_values[i] + top_four_values[j]):
				maximum = (top_four_values[i] + top_four_values[j])

print(maximum)

• 포인트
  • top-1,2,3,4 정보만 알면 된다는 것

• 문제
  • N(1≤N≤200)개의 직사각형(x1,y1,x2,y2, 좌측하단 좌표와 우측상단 좌표의 tuple)이 주어진다. 이 때 정확히 두 개의 직사각형에만 속하는 단위정사각형의 개수를 구하여라.
• 해설

import sys

number_rectangles = int(sys.stdin.readline())
rectangles = [list(map(int, x.split())) for x in sys.stdin.readlines()]
# number_rectangles = 3
# rectangles = [
#     [1, 1, 4, 4],
#     [3, 2, 5, 5],
#     [2, 5, 4, 6]
# ]

intersecting_number = 2

# Create slices
slices = []
for rectangle in rectangles:
    slices.append(rectangle[1])
    slices.append(rectangle[3])
slices = list(set(slices))
slices.sort()  # O(NlogN), slice는 rectangle 개수에 선형적으로 증가하기 때문

# Determine where the rectangle belonging to slices
rectangles.sort(key=lambda x: x[1])  # O(NlogN)
slice_to_rectangles = {idx: [] for idx in range(len(slices) - 1)}

def binary_search(arr, target, low=None, high=None):  # O(logN)
    low, high = low or 0, high or len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] > target:
        return binary_search(arr, target, low, mid)
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)

previous_start_slice_idx = 0
for idx_rec, rectangle in enumerate(rectangles):  # O(NlogN)
    start_slice_idx = binary_search(slices, rectangle[1], low=previous_start_slice_idx)
    end_slice_idx = binary_search(slices, rectangle[3], low=previous_start_slice_idx) - 1
    for idx_slice in range(start_slice_idx, end_slice_idx + 1, 1):
        slice_to_rectangles[idx_slice].append(idx_rec)
    previous_start_slice_idx = start_slice_idx

# Iterate from slices, left x + 1, right x - 1하여 cumulative sum==k 세기
def get_cumulative_sum(list_of_tuples):
    result = [list_of_tuples[0]]
    cum_sum = list_of_tuples[0][1]
    for tp in list_of_tuples[1:]:
        cum_sum += tp[1]
        result.append((tp[0], cum_sum))
    return result

answer = 0
for idx_slice in range(len(slices) - 1):  # O(N^2 * logN)
    rectangle_idxs = slice_to_rectangles[idx_slice]
    sorted_xs = []
    for rectangle_idx in rectangle_idxs:
        sorted_xs.append((rectangles[rectangle_idx][0], +1))
        sorted_xs.append((rectangles[rectangle_idx][2], -1))
    sorted_xs.sort(key=lambda x: x[0])
    xs_with_cumulative_sum = get_cumulative_sum(sorted_xs)
    for ind, (x, cum_sum) in enumerate(xs_with_cumulative_sum):
        if cum_sum == intersecting_number:
            width = xs_with_cumulative_sum[ind + 1][0] - x
            height = slices[idx_slice + 1] - slices[idx_slice]
            answer += width * height
print(answer)

• 포인트
  • sweep line개념으로 y1좌표를 기준으로 아래에서 위로 line segment 만들어서 접근
  • left는 +1, right는 -1을 두고 cumulative sum으로 intersecting 횟수 세기