- https://school.programmers.co.kr/learn/courses/30/lessons/152996
- 키워드 : dp
- 레벨 : 2
from collections import defaultdict
def solution(weights):
answer = 0
info = defaultdict(int)
for w in weights:
# 1:1, 2:3, 3:4, 2:4 비율인 경우
answer += info[w]
answer += info[(w * 2) / 3] + info[(w * 3) / 2]
answer += info[(w * 3) / 4] + info[(w * 4) / 3]
answer += info[(w * 4) / 2] + info[(w * 2) / 4]
info[w] += 1
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/159993
- 키워드 : bfs, dfs
- 레벨 : 2
from collections import deque
def solution(maps):
answer = 0
y = len(maps)
x = len(maps[0])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 주요 좌표 미리 구하기
for i in range(y):
for j in range(x):
if maps[i][j] == "S":
sy, sx = i, j
if maps[i][j] == "L":
ly, lx = i, j
if maps[i][j] == "X":
ey, ex = i, j
def to_lever():
to_lever_cnt = float('inf')
visited = [[False for _ in range(x)] for _ in range(y)]
q = deque()
q.append([sy, sx, 0])
while q:
cy, cx, cnt = q.popleft()
for i in range(4):
ny = cy + dy[i]
nx = cx + dx[i]
# 범위안이고 방문X
if 0 <= ny < y and 0 <= nx < x and not visited[ny][nx]:
# L이면 cnt + 1과 비교
if maps[ny][nx] == "L":
to_lever_cnt = min(to_lever_cnt, cnt + 1)
# 지나갈 수 있으면
elif maps[ny][nx] != "X":
visited[ny][nx] = True
q.append([ny, nx, cnt + 1])
return to_lever_cnt
def to_exit():
to_exit_cnt = float('inf')
visited = [[False for _ in range(x)] for _ in range(y)]
q = deque()
q.append([ly, lx, 0])
while q:
cy, cx, cnt = q.popleft()
for i in range(4):
ny = cy + dy[i]
nx = cx + dx[i]
# 범위안이고 방문X
if 0 <= ny < y and 0 <= nx < x and not visited[ny][nx]:
# E이면 cnt + 1과 비교
if maps[ny][nx] == "E":
to_exit_cnt = min(to_exit_cnt, cnt + 1)
# 지나갈 수 있으면
elif maps[ny][nx] != "X":
visited[ny][nx] = True
q.append([ny, nx, cnt + 1])
return to_exit_cnt
to_lever_cnt = to_lever()
to_exit_cnt = to_exit()
# 이동할 공간이 없는 경우
if to_lever_cnt > 5000 or to_exit_cnt > 5000:
return -1
else:
answer = to_lever_cnt + to_exit_cnt
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/17678
- 키워드 : 구현
- 레벨 : 3
def solution(n, t, m, timetable):
t_table = []
for time in timetable:
hour, minute = time.split(":")
t_table.append((int(hour) * 60 + int(minute)))
now = 540
con = 540
t_table.sort()
while n > 0:
count = 0
for idx, time in enumerate(t_table):
# m명 까지만 수용
if idx > m - 1:
break
# 셔틀시간 안에 온 사람 체크
if now >= time:
count += 1
# 셔틀 시간 갱신
n -= 1
# 더이상의 셔틀이 없을경우
if n == 0:
print(count, t_table)
# 다른사람을 제쳐야할 경우
if m == count:
con = t_table[count-1] - 1
# 제치지 않아도 될 경우
else:
con = now
# 현재시간 갱신
now += t
# 타임 테이블 갱신
t_table = t_table[count:]
# 변환
hour = con // 60
minute = con % 60
if hour < 10:
hour = "0" + str(hour)
if minute < 10:
minute = "0" + str(minute)
answer = str(hour) + ":" + str(minute)
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/60057
- 키워드 : 구현
- 레벨 : 2
한 번에 풀려서 기분 좋았다.
def compress(n, s):
temp = s[:n]
count = 1
compressed_str = ""
i = n
# 마지막 문자열까지 count 체크를 위해 <= 사용
while i <= len(s):
# n개의 문자열이 같을 경우
if s[i:i+n] == temp:
count += 1
# n개의 문자열이 다를 경우
else:
# 숫자 + 문자열 붙이기
if count == 1:
compressed_str += temp
else:
compressed_str += str(count) + temp
# count 초기화 및 검색문자열 초기화
temp = s[i:i+n]
count = 1
i += n
# 처리하지 못한 문자열 더하기
compressed_str += s[i-n:len(s)+1]
return compressed_str
def solution(s):
if len(s) == 1:
return 1
min_length = float('inf')
for i in range(1, len(s)):
compressed_str = compress(i, s)
min_length = min(min_length, len(compressed_str))
return min_length
- https://school.programmers.co.kr/learn/courses/30/lessons/12904
- 키워드 : str
- 레벨 : 3
s의 길이가 그렇게 길지 않고, temp[::-1]이 상수 시간복잡도를 가진 것을 알고있어서 시도해 보았다.
def solution(s):
max_length = 1
for i in range(len(s)):
for j in range(i+1, len(s)):
temp = s[i:j+1]
temp_revserse = temp[::-1]
if temp == temp_revserse:
max_length = max(max_length, len(temp))
return max_length
- https://school.programmers.co.kr/learn/courses/30/lessons/148653
- 키워드 : 경우의 수
- 레벨 : 2
dp로 풀려다가 오히려 복잡해져서 다른분의 풀이를 참고했다.
5일 경우의 다음자리수를 고려하는것이 포인트이다.
def solution(storey):
answer = 0
while storey:
rest = storey % 10
# 6 ~ 9이면 올림
if rest > 5:
answer += (10 - rest)
storey += 10
# 0 ~ 4이면 내림
elif rest < 5:
answer += rest
storey -= rest
# 5일 경우 다음 자리 고려
else:
# 다음자리가 5 ~ 9인 경우 올림
if (storey // 10) % 10 > 4:
answer += rest
storey += 10
else:
answer += rest
storey -= rest
# 다음 자리수 갱신
storey //= 10
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/181187
- 키워드 : math
- 레벨 : 2
import math
def solution(r1, r2):
count = 0
# 1사분면 지군으로 x가 0인 부분은 고려하지 않음
# ㄱㄴ 모양을 기준으로 모든 사분면에 대입해보면 x가 0인 부분도 고려했다고 볼 수 있음
for x in range(1, r2 + 1):
max_y = math.floor(math.sqrt(r2 ** 2 - x ** 2))
# r1 == x인 경우가 답에 포함되야 하므로
min_y = math.ceil(math.sqrt(r1 ** 2 - x ** 2)) if r1 > x else 0
count += max_y - min_y + 1
# 모든 사분면
return count * 4
- https://school.programmers.co.kr/learn/courses/30/lessons/181188
- 키워드 : greedy
- 레벨 : 2
위의 문제와 거의 같다.
def solution(targets):
answer = 0
targets.sort(key = lambda x: (x[1]))
shoot_line = -1
for target in targets:
start, end = target
if start > shoot_line:
shoot_line = end - 0.1
answer += 1
else:
continue
return answer아래는 다른 사람의 풀이이다.
ref) https://beomcoder.tistory.com/70
def solution(t):
missiles, overlap = 0, {'s': 0, 'e': 0}
for s, e in sorted(t):
if overlap['e'] <= s:
missiles+= 1
overlap = {'s': s, 'e': e}
else:
overlap = {'s': max(overlap['s'], s), 'e': min(overlap['e'], e)}
return missiles
- https://school.programmers.co.kr/learn/courses/30/lessons/43238
- 키워드 : 이분탐색
- 레벨 : 3
어렵다.. 결국 다른분의 풀이를 참고했다.
def solution(n, times):
answer = 0
# right는 가장 비효율적으로 심사했을 때 걸리는 시간
# 가장 긴 심사시간이 소요되는 심사관에게 n 명 모두 심사받는 경우이다.
left, right = 1, max(times) * n
while left <= right:
mid = (left+ right) // 2
people = 0
for time in times:
# people 은 모든 심사관들이 mid분 동안 심사한 사람의 수
people += mid // time
# 모든 심사관을 거치지 않아도 mid분 동안 n명 이상의 심사를 할 수 있다면 반복문을 나간다.
if people >= n:
break
# 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 많거나 같은 경우
if people > n:
answer = mid
right = mid - 1
# 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 적은 경우
elif people < n:
left = mid + 1
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/155651
- 키워드 : heap
- 레벨 : 3
import heapq
def solution(book_time):
book_time2 = []
for i in book_time:
temp = []
h, m = i[0].split(":")
total = int(h) * 60 + int(m)
temp.append(total)
h, m = i[1].split(":")
total = int(h) * 60 + int(m) + 10
temp.append(total)
book_time2.append(temp)
heapq.heapify(book_time2)
room = []
time = 0
while book_time2:
# 시간이 다 되었나 체크
for i, _end in enumerate(room):
if time >= _end > 0:
room[i] = 0
# heappop
start, end = heapq.heappop(book_time2)
# 처음 체크
if not room:
room.append(end)
# 방이 존재할 때
else:
heapq.heapify(room)
# 새 손님 객실의 start가 현재 손님이이 있는 객실의 end보다 크면
if room[0] <= start:
room[0] = end
else:
room.append(end)
# 현재 시간 설정
time = start
return len(room)
- https://school.programmers.co.kr/learn/courses/30/lessons/72413
- 키워드 : floyd-warshall
- 레벨 : 3
플로이드 와샬
def solution(n, s, a, b, fares):
matrix = [[float('inf') for j in range(n)] for i in range(n)]
for i in range(n):
matrix[i][i] = 0
for f in fares:
matrix[f[1] - 1][f[0] - 1] = f[2]
matrix[f[0] - 1][f[1] - 1] = f[2]
for k in range(n):
for i in range(n):
for j in range(n):
if matrix[i][k] + matrix[k][j] < matrix[i][j]:
matrix[i][j] = matrix[i][k] + matrix[k][j]
min_value = float('inf')
for i in range(n):
min_value = min(min_value, matrix[s-1][i] + matrix[i][a-1] + matrix[i][b-1])
return min_value
- https://school.programmers.co.kr/learn/courses/30/lessons/81302#fn1
- 키워드 : BFS, DFS
- 레벨 : 2
BFS 기초
# 1. 방문하지 않은 P마다 bfs를 돌리기
# 2. X가 아닌데 멘해튼 거리가 2이하인 경우를 모두 방문하여 P가 있는지 체크
from collections import deque
def bfs(y, x, place, visited):
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
q = deque()
q.append([y, x])
visited[y][x] = True
while q:
cy, cx = q.popleft()
for i in range(4):
ny = cy + dy[i]
nx = cx + dx[i]
if 0 <= ny < 5 and 0 <= nx < 5:
if not visited[ny][nx] and place[ny][nx] != "X":
if abs(y - ny) + abs(x - nx) <= 2:
if place[ny][nx] == "P":
return False
else:
q.append([ny, nx])
visited[ny][nx] = True
return True
def is_ok(place, visited):
for i in range(5):
for j in range(5):
if place[i][j] == "P" and not visited[i][j]:
if not bfs(i, j, place, visited):
return 0
return 1
def solution(places):
answer = []
for place in places:
visited = [[False for _ in range(5)] for _ in range(5)]
answer.append(is_ok(place, visited))
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/154540
- 키워드 : BFS, DFS
- 레벨 : 2
bfs 기초
from collections import deque
def solution(maps):
answer = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
max_y = len(maps)
max_x = len(maps[0])
visited = [[False for _ in range(max_x)] for _ in range(max_y)]
def bfs(y, x):
q = deque()
q.append([y, x])
visited[y][x] = True
cost = int(maps[y][x])
while q:
cy, cx = q.popleft()
for i in range(4):
ny = int(cy) + dy[i]
nx = int(cx) + dx[i]
if 0 <= ny < max_y and 0 <= nx < max_x and maps[ny][nx] != 'X' and not visited[ny][nx]:
visited[ny][nx] = True
cost += int(maps[ny][nx])
q.append([ny, nx])
return cost
for i in range(max_y):
for j in range(max_x):
if maps[i][j] != 'X' and not visited[i][j]:
cost = bfs(i, j)
answer.append(cost)
answer.sort()
if not answer:
return [-1]
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/86971
- 키워드 : union-find
- 레벨 : 2
union-find시 대부분의 경우 유니온 과정 후 루트노트가 아닌 상위노드를 가리키는 경우가 있으므로 한번더 union 해주는 과정이 필요함을 유의하자
from collections import Counter
def find_parent(x, parent):
if parent[x] == x:
return x
else:
return find_parent(parent[x], parent)
def union_parent(a, b, parent):
x = find_parent(a, parent)
y = find_parent(b, parent)
if x < y:
parent[y] = x
else:
parent[x] = y
def solution(n, wires):
answer = float('inf')
for i in range(len(wires)):
parent = [i for i in range(n+1)]
temp = wires[:i] + wires[i+1:]
for j in temp:
union_parent(j[0], j[1], parent)
# 한번 더 찾아서 루트를 가리키게 함
for i in range(len(parent)):
parent[i] = find_parent(i, parent)
counter = Counter(parent[1:])
c_value_list = list(counter.values())
gap = abs(c_value_list[0] - c_value_list[1])
if answer > gap:
answer = gap
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/67257
- 키워드 : index, eval, permutations, del, 구현
- 레벨 : 2
eval은 괄호안의 string을 expression으로 처리하는 함수이다.
파이썬 리스트에서 값을 제거하는 방법은 remove, del 두 가지가 있다.
remove는 리스트의 value를 받아 해당 value가 가장 처음 존재하는 인덱스를 제거하는 함수이고
del은 리스트의 인덱스를 받아 해당 인덱스를 제거하는 함수이다.
import copy
from itertools import permutations
def culculator(split_exp, order):
for op in order:
while op in split_exp:
idx = split_exp.index(op)
result = eval(str(split_exp[idx - 1]) + op + str(split_exp[idx + 1]))
# 계산 후 인덱스 정리
split_exp[idx - 1] = result
del split_exp[idx + 1]
del split_exp[idx]
return split_exp[0]
def solution(expression):
op = ["+", "-", "*"]
# split
split_exp = []
s = 0
for i, val in enumerate(expression):
if val in op:
split_exp.append(expression[s:i])
split_exp.append(expression[i])
s = i+1
# 마지막 숫자
split_exp.append(expression[s:])
op_order = list(permutations(op, 3))
answer_list = []
for order in op_order:
temp = split_exp.copy()
answer_list.append(abs(culculator(temp, order)))
return max(answer_list)
- https://school.programmers.co.kr/learn/courses/30/lessons/12913
- 키워드 : DP
- 레벨 : 2
def solution(land):
# a는 첫번째 칸을 선택한 것
a, b, c, d = land[0]
for i in range(1, len(land)):
_a, _b, _c, _d = a, b, c, d
a = max(_b + land[i][0], _c + land[i][0], _d + land[i][0])
b = max(_a + land[i][1], _c + land[i][1], _d + land[i][1])
c = max(_a + land[i][2], _b + land[i][2], _d + land[i][2])
d = max(_a + land[i][3], _b + land[i][3], _c + land[i][3])
return max(a,b,c,d)
- https://school.programmers.co.kr/learn/courses/30/lessons/42861
- 키워드 : kruskal, union-find, greedy
- 레벨 : 3
kruskal 기초
# kruskal
def find_parent(x, parent):
if parent[x] == x:
return x
return find_parent(parent[x], parent)
def union(a, b, parent):
x = find_parent(a, parent)
y = find_parent(b, parent)
if x < y:
parent[y] = x
else:
parent[x] = y
def solution(n, costs):
total_cost = 0
parent = [i for i in range(n)]
# cost 작은 순으로 정리
costs.sort(key = lambda x: x[2])
for c in costs:
x, y, cost = c
# 아직 연결되지 않았으면
if find_parent(x, parent) != find_parent(y, parent):
total_cost += cost
union(x, y, parent)
return total_cost
- https://school.programmers.co.kr/learn/courses/30/lessons/43164
- 키워드 : bfs, dfs
- 레벨 : 3
- dfs 활용 난이도 상
def solution(tickets):
answer = []
# 그래프 생성
graph = {}
for a, b in tickets:
if a not in graph:
graph[a] = []
graph[a].append(b)
# 경로 정렬 (pop을 사용하므로 알파벳 역순으로 정렬)
for key in graph:
graph[key].sort(reverse=True)
stack = ["ICN"]
# DFS 탐색
while stack:
node = stack[-1]
print(stack)
print(answer)
print(graph)
# 이미 사용한 티켓이라면
if node not in graph or len(graph[node]) == 0:
x = stack.pop()
answer.append(x)
else:
x = graph[node].pop()
stack.append(x)
# 경로 역순으로 반환
return answer[::-1]
- https://school.programmers.co.kr/learn/courses/30/lessons/42627
- 키워드 : heap
- 레벨 : 3
힙 기초
import heapq
def solution(jobs):
# h: 작업 대기시간, 소요시간, 원래 요청시간
length = len(jobs)
ms = 0
# 원래 요청시간 추가
for job in jobs:
job.append(job[0])
heapq.heapify(jobs)
answer_list = []
while jobs:
spend_time = 1
# 작업 대기시간이 0이면 pop
if jobs[0][0] == 0:
wait_time, spend_time, request_time = heapq.heappop(jobs)
answer_list.append(ms + spend_time - request_time)
# 작업 대기시간 감소
for job in jobs:
if job[0] - spend_time < 0:
job[0] = 0
else:
job[0] = job[0] - spend_time
ms += spend_time
heapq.heapify(jobs)
answer = sum(answer_list) // length
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/12978
- 키워드 : dijkstra
- 레벨 : 2
다익스트라는 외우고 가자
import heapq
def solution(N, road, K):
answer = 0
graph = [[] for _ in range(N + 1)]
for r in road:
a, b, cost = r
graph[a].append([b, cost])
graph[b].append([a, cost])
# start -> node까지 가는 최단거리
distance = [float('inf') for _ in range(N+1)]
def dijkstra(start):
q = []
# [현재 start->node까지 가는 비용, 노드]
# (비용, 출발노드) 최소힙이 시작노드와 가장 가까운 거리에 있는 노드를 탐색하는 과정을 대신함
heapq.heappush(q, [0, start])
distance[start] = 0
while q:
_cost, _node = heapq.heappop(q)
# 노드까지 가는 갱신된 비용이 이미 큐에서 뽑은 비용보다 작으면 무시
if distance[_node] < _cost:
continue
# 노드에 연결된 다른 노드들 탐색
for next_node in graph[_node]:
# start -> node -> next_node 비용
cost = distance[_node] + next_node[1]
# 거쳐가는 비용이 더 작다면
if cost < distance[next_node[0]]:
# 코스트 갱신
distance[next_node[0]] = cost
heapq.heappush(q, [cost, next_node[0]])
return
dijkstra(1)
for d in distance[1:]:
if d <= K:
answer += 1
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/49189
- 키워드 : bfs
- 레벨 : 3
dfs로 풀면 시간초과가 난다. 웬만하면 bfs로 푸는 습관을 들여보자.
또한 bfs는 각 노드까지의 최단거리를 보장한다는 점을 잊지말자
from collections import deque
def solution(n, edge):
graph = [[] for _ in range(n+1)]
for e in edge:
a, b = e
graph[a].append(b)
graph[b].append(a)
# 방문여부
visited = [False for _ in range(n+1)]
visited[1] = visited[0] = True
# dist[node] 까지 가는데 걸리는 최소 깊이
dist = [20001 for i in range(n+1)]
dist[1] = dist[0] = 0
q = deque([(1, 0)])
while q:
x, depth = q.popleft()
visited[x] = True
for i in graph[x]:
if not visited[i]:
visited[i] = True
dist[i] = min(dist[i], depth + 1)
q.append((i, depth + 1))
max_value = max(dist)
answer = dist.count(max_value)
return answer- 다익스트라 풀이가 더 직관적이긴하다.
import heapq
def solution(n, edge):
answer = 0
graph = [[] for _ in range(n + 1)]
for e in edge:
a, b = e
# a->b 비용
graph[a].append([b, 1])
graph[b].append([a, 1])
for g in graph:
g.sort()
def dijkstra(start):
distance = [float('inf')] * (n + 1)
distance[start] = 0
q = []
# 시작노드 -> 노드까지 비용, 노드
heapq.heappush(q, [0, start])
while q:
_cost, _node = heapq.heappop(q)
if distance[_node] < _cost:
continue
for next_node in graph[_node]:
# start -> node + node -> next_node 비용
cost = distance[_node] + next_node[1]
# 거쳐가는 비용이 더 작다면
if cost < distance[next_node[0]]:
distance[next_node[0]] = cost
heapq.heappush(q, [cost, next_node[0]])
return distance
distance = dijkstra(1)
# 가장 멀리떨어진 값의 갯수 count
answer = distance.count(max(distance[1:]))
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/131704#
- 키워드 : deque, stack
- 레벨 : 2
그림 그리면서 풀면 쉬움
from collections import deque
def solution(order):
count = 0
order = deque(order)
container = deque([i+1 for i in range(len(order))])
# stack
sub_container = []
while container:
if order and container[0] == order[0]:
order.popleft()
container.popleft()
count += 1
elif order and container[0] != order[0]:
x = container.popleft()
sub_container.append(x)
while sub_container and order and (sub_container[-1] == order[0]):
order.popleft()
sub_container.pop()
count += 1
return count
- https://school.programmers.co.kr/learn/courses/30/lessons/12971
- 키워드 : DP
- 레벨 : 3
레벨 4급이라고 생각
def solution(sticker):
n = len(sticker)
if n == 1:
return sticker[0]
elif n == 2:
return max(sticker[0], sticker[1])
# 첫 번째 스티커를 뜯는 경우
dp = [0] * n
dp[0] = sticker[0]
dp[1] = dp[0]
for i in range(2, n - 1):
dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i])
# 첫 번째 스티커를 뜯지 않는 경우
dp2 = [0] * n
dp2[0] = 0
dp2[1] = sticker[1]
for i in range(2, n):
dp2[i] = max(dp2[i - 1], dp2[i - 2] + sticker[i])
# 두 경우 중 최댓값 반환
return max(dp[-2], dp2[-1])
- https://school.programmers.co.kr/learn/courses/30/lessons/12905
- 키워드 : DP
- 레벨 : 2
import copy
def solution(board):
# dp[i][j]가 현재 위치에서 가질 수 있는 가장 긴 변의 길이라고 정의
dp = copy.deepcopy(board)
length = 0
# y가 1일 경우
if len(dp) == 1:
for i in range(len(dp[0])):
if dp[0][i] == 1:
return 1
return length
# x가 1일 경우
if len(dp[0]) == 1:
for i in range(len(dp)):
if dp[i][0] == 1:
return 1
return length
for i in range(1, len(dp)):
for j in range(1, len(dp[0])):
if dp[i][j] == 1:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
length = max(length, dp[i][j])
return length**2
- https://school.programmers.co.kr/learn/courses/30/lessons/67258?language=python3
- 키워드 : Counter, two-pointer, 구현
- 레벨 : 3
파이썬에서 set이나 slice은 O(n)의 시간복잡도 가지므로 반복문 안에서는 사용하지 않도록 하자.
Counter와 투 포인터 알고리즘을 사용하여 구해야 시간초과가 나지 않는다
from collections import Counter
def solution(gems):
answer = []
kind = len(set(gems))
c = Counter(gems[:kind-1])
# two-pointer
left = 0
for right in range(kind-1, len(gems)):
c[gems[right]] += 1
while len(c) == kind:
answer.append([left+1, right+1])
c[gems[left]] -= 1
if(c[gems[left]] == 0):
del c[gems[left]]
left += 1
answer = sorted(answer, key = lambda x: (x[1]-x[0], x[0]))
return answer[0]
- https://school.programmers.co.kr/learn/courses/30/lessons/42885
- 키워드 : greedy
- 레벨 : 2
그리디 알고리즘 완전기초
from collections import deque
def solution(people, limit):
answer = 0
people.sort(reverse = True)
q = deque(people)
while q:
cur_w = q.popleft()
while len(q) > 0:
if cur_w + q[-1] <= limit:
cur_w += q.pop()
else:
break
answer += 1
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/178870
- 키워드 : two-pointer
- 레벨 : 2
def solution(sequence, k):
# 각 원소를 누적합으로 변환
for i in range(1, len(sequence)):
sequence[i] += sequence[i-1]
start = 0
end = 1
min_length = float('inf')
result = []
while end <= len(sequence):
if start == 0:
current_sum = sequence[end-1]
else:
current_sum = sequence[end-1] - sequence[start-1]
if current_sum < k:
if end == len(sequence):
break
end += 1
elif current_sum == k:
if end - start < min_length:
min_length = end - start
result = [start, end-1]
start += 1
else:
start += 1
return result
- https://school.programmers.co.kr/learn/courses/30/lessons/64064
- 키워드 : permutation
- 레벨 : 3
dfs로 푸는 사람도 있지만 permutation으로 푸는게 나은 것 같다.
왜 조합을 쓰면 안되는지는 아래 링크에 잘 설명해준 분이 있다 (_ _)
https://school.programmers.co.kr/questions/23330
마지막에 set으로 중복을 없애야 하는데 python에서 list는 set을 적용할 수 없지만 tuple은 적용할 수 있으므로 tuple로 저장하는 것을 놓치지 말자
from itertools import permutations
def correct(arr1, arr2):
for i in range(len(arr1)):
if len(arr1[i]) != len(arr2[i]):
return False
for j in range(len(arr1[i])):
if arr2[i][j] != "*" and (arr1[i][j] != arr2[i][j]):
return False
return True
def solution(user_id, banned_id):
answer = 0
per_list = list(permutations(user_id, len(banned_id)))
temp_list = []
for per in per_list:
if correct(per, banned_id):
temp_list.append(per)
for i in range(len(temp_list)):
temp_list[i] = tuple(sorted(temp_list[i]))
answer = len(set(temp_list))
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/42579
- 키워드 : dict, sort
- 레벨 : 3
defaultdict에서 n중 배열 표현을 하고 싶으면 lambda를 활용하면 됨
ex) defaultdict(lambda: [])
from collections import defaultdict
def solution(genres, plays):
answer = []
temp = defaultdict(lambda: [0, []])
for idx, (genre, play) in enumerate(zip(genres, plays)):
temp[genre][0] += play
temp[genre][1].append([play, idx])
# 속한노래가 많이 재생된 장르 정렬
temp = sorted(temp.items(), key = lambda x: -x[1][0])
# 장르내에서 많이 재생된 노래 정렬, 고유번호가 낮은 노래 정렬
for t in temp:
t[1][1].sort(key = lambda x: (-x[0], x[1]))
for t in temp:
cnt = 0
for num in t[1][1]:
if cnt >= 2:
break
answer.append(num[1])
cnt += 1
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/12987
- 키워드 : heap
- 레벨 : 3
최대 최소값 들어가면 90% 이상은 무조건 시간복잡도를 O(NlogN)에 맞춰야 함
대부분 heap 아니면 stack으로 구현
import heapq
def solution(A, B):
answer = 0
A = list(map(lambda x: -x, A))
B = list(map(lambda x: -x, B))
heapq.heapify(A)
heapq.heapify(B)
while B and A:
a = heapq.heappop(A)
b = heapq.heappop(B)
if -b > -a:
answer += 1
else:
heapq.heappush(B, b)
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/42883
- 키워드 : stack
- 레벨 : 2
def solution(number, k):
answer = []
for num in number:
while k > 0 and answer and answer[-1] < num:
answer.pop()
k -= 1
answer.append(num)
return ''.join(answer[:len(number)-k])
- https://school.programmers.co.kr/learn/courses/30/lessons/42884
- 키워드 : greedy
- 레벨 : 3
- 전형적인 그리디 문제, 문제를 이해하면 쉽지만 아니면 어려움. 문제를 쉽게 바꾸는 연습부터 하자
def solution(routes):
routes.sort(key = lambda x : (x[1]))
answer = 0
divide_bar = -30001
print(routes)
for route in routes:
if route[0] <= divide_bar:
continue
else:
divide_bar = route[1]
answer += 1
return answer다른풀이
def solution(routes):
camera = 0
routes.sort(key = lambda x: x[1])
overlap = {'s': -30001, 'e': -30001}
for route in routes:
if overlap['e'] < route[0]:
overlap['s'] = route[0]
overlap['e'] = route[1]
camera += 1
else:
overlap['s'] = max(overlap['s'], route[0])
overlap['e'] = min(overlap['e'], route[1])
return camera
- https://school.programmers.co.kr/learn/courses/30/lessons/42898
- 키워드 : dp
- 레벨 : 3
전형적인 dp 문제, 패딩하면 쉬움 처음 풀이는 난잡했지만 경우의 수 따지기에는 좋아서 넣어둠
(puddles y, x 좌표에 유의하자)
처음풀이 :
def solution(m, n, puddles):
dp = [[0 for i in range(0, m+1)] for _ in range(0, n+1)]
for y in range(0, n+1):
for x in range(0, m+1):
if y == 0 or x == 0 or [x, y] in puddles:
dp[y][x] = float('inf')
elif y == 1 and x == 1:
dp[y][x] = 1
elif dp[y-1][x] == float('inf') and dp[y][x-1] != float('inf'):
dp[y][x] = dp[y][x-1]
elif dp[y-1][x] != float('inf') and dp[y][x-1] == float('inf'):
dp[y][x] = dp[y-1][x]
elif dp[y-1][x] == float('inf') and dp[y][x-1] == float('inf'):
dp[y][x] = float('inf')
else:
dp[y][x] = dp[y][x-1] + dp[y-1][x]
if dp[n][m] == float('inf'):
return 0
return dp[n][m] % 1000000007최적화:
def solution(m, n, puddles):
dp = [[0 for i in range(0, m+1)] for _ in range(0, n+1)]
dp[1][1] = 1
for y in range(1, n+1):
for x in range(1, m+1):
if [y, x] == [1, 1] or [x, y] in puddles:
continue
else:
dp[y][x] = dp[y][x-1] + dp[y-1][x]
return dp[n][m] % 1000000007
- https://school.programmers.co.kr/learn/courses/30/lessons/43163
- 키워드 : bfs, dfs
- 레벨 : 3
기초 bfs, dfs
전역변수 없이 풀어보기, 만약 visited가 일차원 배열이라면 set()을 사용하면 O(n) -> O(1)로 줄이기 가능\
풀이1
answer = 51
def dfs(begin, target, words, visited, count):
global answer
if begin == target:
answer = min(answer, count)
return
for idx, word in enumerate(words):
if visited[idx]:
continue
same_count = 0
for i in range(len(word)):
if begin[i] == word[i]:
same_count += 1
# 하나만 다르고 나머지 같다면
if same_count == (len(word) - 1):
visited[idx] = True
dfs(word, target, words, visited, count + 1)
visited[idx] = False
def solution(begin, target, words):
global answer
visited = [False for _ in range(len(words))]
dfs(begin, target, words, visited, 0)
if answer == 51:
return 0
return answer풀이2
def dfs(begin, target, words, visited, count):
if begin == target:
return count
min_count = float('inf')
for i in range(len(words)):
temp = 0
if visited[i]:
continue
for j in range(len(words[i])):
if begin[j] == words[i][j]:
temp += 1
if temp == (len(words[i]) - 1):
visited[i] = True
cur_count = dfs(words[i], target, words, visited, count + 1)
min_count = min(min_count, cur_count)
visited[i] = False
return min_count
def solution(begin, target, words):
visited = set()
count = dfs(begin, target, words, visited, 0)
return count if count != float('inf') else 0
- https://school.programmers.co.kr/learn/courses/30/lessons/12927
- 키워드 : heap
- 레벨 : 3
최대힙을 사용하는 문제
힙의 최대값에서 1을 빼는 것을 x = heapq.heappop() 후 heapq.heappush(heap, x + 1)로 표현한 것이 유용한 듯
import heapq
def solution(n, works):
# 최대힙 만들기
h = [-x for x in works]
heapq.heapify(h)
for i in range(n):
work = heapq.heappop(h)
# 빈 경우
if not h:
break
if work < 0:
heapq.heappush(h, work + 1)
answer = sum(list(map(lambda x: x**2, h)))
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/43162#
- 키워드 : union-find
- 레벨 : 3
bfs, dfs 문제인데 union-find가 더 간단함
마지막에 한번더 find를 하지 않으면 안되는 함정이 숨어 있음
def findParent(arr, x):
if(arr[x] == x):
return x
return findParent(arr, arr[x])
def unionParent(arr, a, b):
a = findParent(arr, a)
b = findParent(arr, b)
if(a < b):
arr[b] = a
else:
arr[a] = b
def solution(n, computers):
arr = [i for i in range(n)]
for i in range(n):
for j in range(n):
if i != j and computers[i][j] == 1:
unionParent(arr, i, j)
# [0,0,1,1,1,1,0]일 경우 모든 노드의 parent가 0을 가리키고 있으므로 한 번더 정리
for i in range(len(arr)):
arr[i] = arr[arr[i]]
return len(set(arr))
- https://school.programmers.co.kr/learn/courses/30/lessons/43165#
- 키워드 : dfs, bfs
- 레벨 : 2
간단하지만 여러 풀이가 있음
from itertools import product
def solution(numbers, target):
# numbers가 [a1, b1, c1] 이면 [(a1, -a1), (b1, -b1), (c1, -c1)] 형태로 변환
l = [(x, -x) for x in numbers]
# product(*l)을 하면 각 요소들의 모든 경우에 수 생성 ex) (a1, b1, c1), (-a1, b1, c1), (a1, -b1, c1) ... 등 총 8개 생성
s = list(map(sum, product(*l)))
return s.count(target)count = 0
def dfs(numbers, target, cnt):
global count
if cnt == len(numbers):
if sum(numbers) == target:
count += 1
return
else:
dfs(numbers, target, cnt+1)
numbers[cnt] *= -1
dfs(numbers, target, cnt+1)
return
def solution(numbers, target):
global count
dfs(numbers, target, 0)
return countcount = 0
def dfs(numbers, cur, target):
global count
if not numbers:
if cur == target:
count += 1
return
else:
return
x = numbers[0]
dfs(numbers[1:], cur + x, target)
dfs(numbers[1:], cur - x, target)
return
def solution(numbers, target):
global count
dfs(numbers, 0, target)
return count
- https://school.programmers.co.kr/learn/courses/30/lessons/42628
- 키워드 : heap, 구현
- 레벨 : 3
파이썬에서 제공하는 heapq은 최소힙으로 최대힙은 제공하지 않는다. 최대힙처럼 사용하기 위해서는 만들기 위해서는 -1을 곱하고 heapify를 한 후 heapq.heappop()을 하면 최대힙의 pop과 같은 효과를 얻을 수 있다.
아래 문제에서는 최대힙의 pop 기능만 가능하면 되므로 총 3가지 방법으로 풀 수 있다.
1. 위에 설명한 방법
2. heap을 역순으로 sort후 첫번째 원소만 버리고 슬라이스, 이후 heapq.heapify
3. heapq.nlargest(n, list)를 사용하여 list에서 큰 순서대로 n개 뽑은 후 슬라이스, 이후 heapq.heapify
1보단 2,3이 빠르고 2는 nlogk (k는 nlargest에서 몇개를 뽑을 건지), 3은 nlog의 시간복잡도를 가지지만
여기서는 어차피 k = n이므로 시간복잡도는 거의 같다고 볼 수 있다.
import heapq
from collections import deque
def solution(operations):
dq = deque(operations)
# 파이썬은 최소힙만 지원, 최대힙은 -1 곱한다음 정렬후 다시 -1 곱해서 만들기
heap = []
while dq:
x = dq.popleft()
op1 = x.split(" ")[0]
op2 = x.split(" ")[1]
if op1 == "I":
heapq.heappush(heap, int(op2))
elif op1 == "D" and heap:
# 최솟값 삭제
if op2 == "-1":
heapq.heappop(heap)
# 최댓값 삭제
else:
# heap = sorted(heap, reverse = True)[1:]
# heapq.nlargest(n, list)는 list에서 큰 순서로 n개를 뽑아낸다 (ma)
heap = heapq.nlargest(len(heap), heap)[1:]
heapq.heapify(heap)
# heap = list(map(lambda x: -x, heap))
# heapq.heapify(heap)
# heapq.heappop(heap)
# heap = list(map(lambda x: -x, heap))
# heapq.heapify(heap)
print(heap)
if not heap:
return [0, 0]
else:
return [max(heap), min(heap)]
- https://school.programmers.co.kr/learn/courses/30/lessons/43105
- 키워드 : dp
- 레벨 : 3
def solution(triangle):
dp = [[0]*(i+1) for i in range(len(triangle))]
dp[0][0] = triangle[0][0]
for i in range(1, len(dp)):
for j in range(i):
dp[i][j] = max(dp[i][j], dp[i-1][j] + triangle[i][j])
dp[i][j+1] = dp[i-1][j] + triangle[i][j+1]
return max(dp[-1])
- https://school.programmers.co.kr/learn/courses/30/lessons/118667
- 키워드 : queue, deque, two_pointer
- 레벨 : 2
def solution(queue1, queue2):
count = 0
q = queue1 + queue2
if sum(q) % 2 != 0:
return -1
if max(q) > int(sum(q) / 2):
return -1
# q1: [a:b], q2:[b:] + [0:a]
max_idx = len(q)
q1_idx = 0
q2_idx = len(queue2)
q1_sum = sum(queue1)
q2_sum = sum(queue2)
while q1_sum != q2_sum:
if q2_idx >= max_idx:
q2_idx = 0
if q1_idx >= max_idx:
return -1
if q1_sum > q2_sum:
q1_sum -= q[q1_idx]
q2_sum += q[q1_idx]
q1_idx += 1
else:
q2_sum -= q[q2_idx]
q1_sum += q[q2_idx]
q2_idx += 1
count += 1
return count
- https://school.programmers.co.kr/learn/courses/30/lessons/154538
- 키워드 : dp
- 레벨 : 2
def solution(x, y, n):
INF = float('inf')
dp = [INF] * (y + 1)
dp[x] = 0
# dp의 i = 계산값, value = 카운트
for i in range(x, y+1):
if dp[i] == INF:
continue
if i + n <= y:
dp[i + n] = min(dp[i + n], dp[i] + 1)
if i * 2 <= y:
dp[i * 2] = min(dp[i * 2], dp[i] + 1)
if i * 3 <= y:
dp[i * 3] = min(dp[i * 3], dp[i] + 1)
if dp[y] == INF:
return -1
else:
return dp[y]
- https://school.programmers.co.kr/learn/courses/30/lessons/42626
- 키워드 : heap
- 레벨 : 2
- heap은 우선순위큐의 한 종류로 완전 이진 트리(Complete Binary Tree)이며, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다.
- 파이썬에는 리스트 기반의 우선순위큐(PriorityQueue)와 힙큐(headq)를 모두 지원하지만 힙큐가 시간복잡도 상으로 더 좋으므로 힙큐(heapq) 만 알아두면 된다.
- 시간복잡도 관련 :
데이터 개수가 N개일 때, 리스트 기반 우선순위 큐 구현 시 최악의 경우에 시간 복잡도는 O(N^2)입니다. 반면, 힙 자료구조를 사용하면 최악의 경우에도 시간 복잡도가 O(NlogN)입니다. 힙 자료구조의 경우, N개의 데이터를 삽입하고 우선순위에 맞게 데이터를 탐색하는 과정은 모두 O(logN) 의 연산을 N번 반복하므로 O(NlogN) 만큼의 시간이 소요됩니다. 따라서 전체 연산 횟수는 2NlogN이므로 전체 시간 복잡도는 빅오 표기법에 따라 O(NlogN)입니다. 이처럼 시간 복잡도 측면에서 데이터의 개수가 많아질수록 힙 자료구조를 활용하여 우선순위 큐를 구현했을 때가 리스트를 활용할 때보다 훨씬 효율적이라는 것을 알 수 있습니다.
- Tips:
h가 heap일 때, h[0]은 항상 최솟값이지만, h[-1]은 항상 최댓값이 아닐 수 있다.
import heapq
def solution(scoville, K):
count = 0
heapq.heapify(scoville)
while scoville[0] < K:
# 힙이의 길이가 1이하인 경우
# => 모든 음식의 스코빌 지수 K이상으로 만들 수 없음
if len(scoville) <= 1:
return -1
first = heapq.heappop(scoville)
second = heapq.heappop(scoville)
heapq.heappush(scoville, (first + second * 2))
count += 1
return count
- https://school.programmers.co.kr/learn/courses/30/lessons/154539
- 키워드 : stack
- 레벨 : 2
heapq 풀이
import heapq
def solution(numbers):
answer = [-1 for _ in range(len(numbers))]
h = []
for idx, value in enumerate(numbers):
while h and h[0][0] < value:
_, _idx = heapq.heappop(h)
answer[_idx] = value
heapq.heappush(h, [value, idx])
return answer
stack 풀이
def solution(numbers):
answer = [-1 for _ in range(len(numbers))]
stack = []
for i in range(len(numbers)):
# 스택이 비어있지 않고, 스택에 마지막으로 들어온 인덱스에 해당하는 numbers의 값보다 현재 numbers의 값이 크다면 뒷 큰 수이므로
while stack and numbers[stack[-1]] < numbers[i]:
# answer의 해당 인덱스의 자리에 numbers[i] (뒷 큰 수 삽입)
answer[stack.pop()] = numbers[i]
stack.append(i)
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/76502
- 키워드 : stack
- 레벨 : 2
def check(str_list):
stack = []
for _str in str_list:
if _str in ('[', '(', '{'):
stack.append(_str)
else:
if not stack: return False
x = stack.pop()
if _str == ']' and x != '[':
return False
elif _str == ')' and x != '(':
return False
elif _str == '}' and x != '{':
return False
if stack: return False
return True
def solution(s):
cnt = 0
for i in range(len(s)):
u = s[:i]
v = s[i:]
if check(v+u):
cnt +=1
return cnt
- https://school.programmers.co.kr/learn/courses/30/lessons/72411
- 키워드 : dictionary, combinations, Counter, sort, join, 구현
- 레벨 : 2
- 여러가지 라이브러리 기능 사용하기 좋은 문제
from itertools import combinations
from collections import Counter
def solution(orders, course):
answer = []
for i in course:
counters = Counter()
# course 개수별 Counter 세기
for order in orders:
# XW와 WX를 동일하게 하기 위해 str 사전순 정렬
order = ''.join(sorted(list(order)))
# combination 결과 join으로 묶고
result = map(''.join, combinations(order, i))
# 카운터 업데이트
counters.update(result)
# course별 max 값가진 keys 찾기, 0이면 스킵
if not counters:
continue
max_value = max(counters.values())
# 최소 value값이 2이상이어야 함
if max_value < 2:
continue
max_keys = [key for key, value in counters.items() if value == max_value]
answer.extend(max_keys)
# 사전순 정렬
answer.sort()
return answer
- https://school.programmers.co.kr/learn/courses/30/lessons/132265
- 키워드 : Counter, defaultdict
- 레벨 : 2
- 처음이 set과 slice로 풀 수 있을 것 같았지만 시간초과였다.
- defaultdict은 dict의 서브클래스로 dict은 연산시 key가 존재하지 않으면 에러가 나지만 defaultdict은 key가 존재하지 않을시 자동으로 추가해주는 장점이 있다.
from collections import Counter, defaultdict
def solution(topping):
answer = 0
me = Counter(topping)
bro = defaultdict(int)
for t in topping:
bro[t] += 1
me[t] -= 1
if me[t] == 0:
del me[t]
if len(bro) == len(me):
answer += 1
return answer
'Python' 카테고리의 다른 글
| 프로그래머스 Level2 문제 모음[Python] (0) | 2022.09.29 |
|---|---|
| Python 알고리즘 라이브러리 모음 (0) | 2022.09.29 |