목차
- 유사 삼합
- 나만의 atoi
- 직사각형들과 직사각형
- 의리의 짐싸기
- 효율적인 문제 풀이
1. 유사 삼합
풀이
/*
* 3개의 숫자를 뽑는 것은 brute-force로 할 경우
* nC3 = n*(n-1)*(n-3) / (3*2*1) 가지이므로, O(n^3)에 해당합니다.
* 숫자를 정렬한 후에 투포인터 알고리즘을 사용할 경우 O(n^2)까지 줄일 수 있습니다.
* left를 고정하고 right와 mid를 결정하는 방식입니다.
*/
def solution(arr, target):
N = len(arr)
closest_diff = float('inf')
closest_sum = 0
arr.sort()
for left in range(N-2):
if left > 0 and arr[left] == arr[left-1]:
continue
mid = left + 1
right = N - 1
while mid < right:
curr_sum = arr[left] + arr[mid] + arr[right]
diff = abs(target-curr_sum)
if diff < closest_diff:
closest_diff = diff
closest_sum = curr_sum
elif diff == closest_diff and closest_sum > curr_sum:
closest_sum = curr_sum
if curr_sum < target:
mid += 1
elif curr_sum > target:
right -= 1
else:
return target
return closest_sum
Test case
# 테스트 1
입력값 〉 [2, 3, 5, 10, 12, 15], 21
기댓값 〉 20
# 테스트 2
입력값 〉 [-5, 2, 4, 10, 23], 15
기댓값 〉 162. 나만의 atoi
풀이
/*
* 기본적인 정수 변환 기능을 구현하는 문제입니다.
* 문제에서 제시하는 추가 기능을 적절하게 잘 구현하는 것이 핵심입니다.
* 다양한 테스트케이스에 대비하여 빈틈없는 코드를 짜는 습관을 들입시다.
*/
MAX_INT = 2**31 - 1
MIN_INT = -2**31
def solution(s):
num = []
s = s.lstrip()
for i in range(len(s)):
if s[i] == '-' or s[i] == '+':
num += [s[i]]
if '0' <= s[i] <= '9':
while i < len(s) and s[i] == '0':
i += 1
if not('0' <= s[i] <= '9'):
return 0
while i < len(s) and '0' <= s[i] <= '9':
num += [s[i]]
i += 1
return clip_num(num)
return 0
def clip_num(s):
if len(s) == 0:
return 0
elif s[0] == '-' and len(s) > len(str(MIN_INT)):
return MIN_INT
elif s[0] == '+' and len(s) > len(str(MAX_INT)) + 1:
return MAX_INT
elif len(s) > len(str(MAX_INT)):
return MAX_INT
else:
num = int(''.join(s))
return max(MIN_INT, min(MAX_INT, num))
Test case
# 테스트 1
입력값 〉 " - 42514243zero123base"
기댓값 〉 -42514243
# 테스트 2
입력값 〉 " + 00051241231004242542514243_41251243"
기댓값 〉 21474836473. 직사각형들과 직사각형
풀이
def solution(heights):
stack = [] # 스택을 활용하여 높이의 인덱스를 저장
max_area = 0 # 최대 직사각형 넓이
n = len(heights)
for i in range(n + 1): # 마지막에 0을 추가한 효과를 위해 (높이 비교)
h = heights[i] if i < n else 0 # 마지막 인덱스 이후에는 높이 0을 추가
# 스택이 비어있지 않고, 현재 높이가 스택의 top보다 작으면 계산
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()] # 스택에서 pop한 높이
width = i if not stack else i - stack[-1] - 1 # 폭 계산
max_area = max(max_area, height * width) # 최대 넓이 갱신
# 현재 인덱스를 스택에 push
stack.append(i)
return max_areaTest case
# 테스트 1
입력값 〉 [5, 2, 1, 3, 4, 2, 5]
기댓값 〉 8
# 테스트 2
입력값 〉 [3, 4, 5, 6, 5, 4, 3, 2, 1]
기댓값 〉 214. 의리의 짐싸기
풀이
def solution(N, K1, K2, W, V):
dp = [[[0 for _ in range(K2 + 1)] for _ in range(K1 + 1)] for _ in range(2)]
for i in range(N):
for k1 in range(K1 + 1):
for k2 in range(K2 + 1):
val1, val2 = 0, 0
if k1 >= W[i]:
val1 = dp[(i-1)%2][k1 - W[i]][k2] + V[i]
if k2 >= W[i]:
val2 = dp[(i-1)%2][k1][k2 - W[i]] + V[i]
dp[i%2][k1][k2] = max(dp[(i-1)%2][k1][k2], val1, val2)
return dp[(N-1)%2][K1][K2]Test case
# 테스트 1
입력값 〉 8, 10, 15, [6, 4, 5, 6, 8, 9, 10, 3], [10, 4, 6, 8, 2, 8, 5, 6]
기댓값 〉 34
# 테스트 2
입력값 〉 14, 13, 18, [3, 4, 1, 5, 2, 5, 2, 3, 4, 2, 3, 4, 1, 3], [7, 6, 3, 15, 18, 12, 7, 16, 11, 8, 13, 14, 7, 3]
기댓값 〉 1215. 효율적인 문제 풀이
풀이
import heapq
def prim(graph, start_node):
mst = []
heap = []
weights = [float('inf')] * len(graph)
connected = set()
weights[start_node] = 0
connected.add(start_node)
for node, weight in graph[start_node]:
heapq.heappush(heap, (weight, start_node, node))
weight_sum = 0
while heap:
weight, a, b = heapq.heappop(heap)
if (weights[b] <= weight) or (b in connected):
continue
weights[b] = weight
connected.add(b)
weight_sum += weight
mst.append((weight, a, b))
adj_list = graph[b]
for n, w in adj_list:
if weights[n] > w:
heapq.heappush(heap, (w, b, n))
return weight_sum
def get_connected(graph, node):
connected = [node]
stack = [adj_node for adj_node, weight in graph[node]]
while stack:
adj = stack.pop()
if adj in connected:
continue
connected.append(adj)
stack += [adj_node for adj_node, weight in graph[adj]]
return connected
def solution(N, relations):
graph = [[] for _ in range(N)]
for a, b, w in relations:
graph[a].append((b, w))
graph[b].append((a, w))
all_nodes = list(range(N))
connected_graphs = []
while all_nodes:
connected = get_connected(graph, all_nodes[0])
for node in connected:
all_nodes.remove(node)
connected_graphs.append(connected)
result = 0
for connected in connected_graphs:
result += 30
result += prim(graph, connected[0])
return result
Test case
# 테스트 1
입력값 〉 6, [[2, 3, 15], [1, 5, 10], [3, 4, 25], [1, 2, 27], [1, 4, 29], [2, 5, 5]]
기댓값 〉 115출처
해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.
모든 자료는 저작권법에 의하여 보호받는 저작물로서 이에 대한 무단 복제 및 배포를 원칙적으로 금합니다.
Comment