[이분탐색] 금과 은 운반하기 (Lv.3)
걸린 시간
1시간 초과
접근 방식
그냥 한 곳의 금이든 은이든 최대치를 가져간다고 가정하고 풀어보려고 했다.
g/t, s/t 중 가장 낮은 곳부터 다 가져올 때
((min(a, g) // w)[왕복 횟수] * 2 * t) + (t if (min(a, g) % w) != 0[잔여를 가져오나 여부]) else 0)이게 한 도시에서 금 혹은 은을 다 가져오는데 걸리는 시간으로 계산하고 각 도시별로 최솟값을 구한 뒤 금 과 은 중 더 짧은 시간으로 정답을 구하려 했다.
하지만 w와 a 혹은 b의 양에 따라 변수가 많았다.
결국 해답을 찾지 못하고 해설을 찾아보았다.
답은 이분 탐색으로 걸리는 시간을 먼저 설정해두고,
그 시간 안에 가져올 수 있는지 여부로 시간 후보를 좁혀나가는 방식이었다.
정답 코드
def solution(a, b, g, s, w, t):
left = 0
right = 10 ** 15
while left <= right:
mid = (left + right) // 2
gold = 0
silver = 0
gs = 0
for i in range(len(g)):
P = mid // (2 * t[i]) * w[i] + (w[i] if mid % (2 * t[i]) >= t[i] else 0)
gold += min(P, g[i])
silver += min(P, s[i])
gs += min(P, g[i] + s[i])
if gold >= a and silver >= b and gs >= a + b:
right = mid - 1
answer = mid
else:
left = mid + 1
return answer배운점
문제를 보는 시각을 시간을 찾아가는게 아닌 시간을 정해두고 조건이 맞는지를 검사하면서 가능한 시간 후보를 좁히는 문제 풀이 방법이 꽤나 신선했다.
최대 시간이 10^9 * 200000 이므로 이분 탐색을 하면 대충 40~50번에 끝나므로 적절한 방법이라고 볼 수 있다.
[구현, 문자열] 올바른 괄호의 갯수 (Lv.4)
걸린 시간
20분
접근 방식
초기값을 ( 으로 설정하고 그 뒤에 ( 혹은 ) 을 추가하는 방식으로 분기를 나눈다.
두 분기의 경우의 수를 더한 값이 리턴 값이다.
단, (가 n개가 되면 나머지 자리는 다 ) 이므로 기저 조건이 된다.
정답 코드
def search(n, cnt):
if cnt[0] == n:
return 1
open, close = cnt
return search(n, [open+1, close]) + (search(n,[open, close+1]) if open != close else 0)
def solution(n):
answer = d(n,[1,0])
return answer배운점
[구현, 문자열] 불량 사용자 (Lv.3)
걸린 시간
50분
접근 방식
- banned_id마다 매칭되는 user_id 찾기
- 매칭되는 경우의 수로 result 뽑기
3번의 경우
"frd" : 0, 1
"*rodo" : 0, 2
"**" : 3, 4
"**" : 3, 4
이런 식으로 match에 [[0,1],[0,2],[3,4],[3,4]]를 저장하고
여기에서 가능한 경우의 수를 다 조사한다.
정답 코드
def f(match, idx, pre):
if idx == len(match):
return [sorted(pre)]
result = []
for i in match[idx]:
if i not in pre:
res = f(match, idx+1, pre + [i])
if len(res) > 0:
result.extend(res)
return result
def search(banned, user_id):
result = []
for num, user in enumerate(user_id):
if len(user) != len(banned):
continue
is_result = True
for i in range(len(user)):
if banned[i] == "*":
continue
if banned[i] != user[i]:
is_result = False
if is_result:
result.append(num)
return result
def solution(user_id, banned_id):
match = []
for banned in banned_id:
match.append(search(banned, user_id))
answer = f(match, 0, [])
return len(set(tuple(x) for x in answer))배운점
경우의 수를 저장하는 과정에서
[[[[[0, 2, 3, 4]], [[0, 2, 3, 4]]]], [[[[0, 1, 3, 4]], [[0, 1, 3, 4]]], [[[1, 2, 3, 4]], [[1, 2, 3, 4]]]]]이런식으로 중복 리스트 현상이 생겨서 좀 고생했다.
리스트의 extend 함수를 통해 이를 해결했다.
