[2023 Kakao Blind Recruitment] 택배 배달과 수거하기

김아현·2023년 7월 9일
0

코딩테스트

목록 보기
16/26
post-custom-banner

이 문제는 그래도 다른 문제들에 비해 읽기 쉬웠다
핵심만 남겨놓고 보면, 택배든 수거든 가장먼것부터 가져오고, cap이 남아있다면 겸사겸사 가장 먼것 중에서 남은 칸을 채워 쓰는 방법이 가장 효율적이다.

이렇게 생각해놓고 보면 코드를 정말 논리 그대로 반복문과 리스트로 풀면 좋겠지만 뭔가 그럼에도 사용할 수 있는 방법은 없을까? 하다가 bfs로 풀어볼까? 싶어서 바로 짜보았다.

1차 작성 코드

from collections import deque
# 가장 먼것부터 배달
# 가장 먼것부터 회수, 칸이 남는 한에 회수
def solution(cap, n, deliveries, pickups):
    ans = 0
    d_dq = deque()
    p_dq = deque()
    
    for i in range(n):
        if deliveries[i] != 0:
            d_dq.append(i)
        if pickups[i] != 0:
            p_dq.append(i)
            
    while d_dq and p_dq:
        d = d_dq.popleft()
        p = p_dq.popleft()
        ans += (max(d,p) + 1) * 2

	# 남은 배달 마치기
    if d_dq:
        cur = cap
        while d_dq:
            tmp = d_dq.popleft()
            cur = max(cur, tmp) #여기서 부터 꼬임
        ans += cur
    
    if p_dq:
        cur = cap
        while p_dq:
            tmp = p_dq.popleft()
            cur = max(cur, tmp)
        ans += cur
    
    
    return ans

다른 풀이

from collections import deque
# 가장 먼것부터 배달
# 가장 먼것부터 회수, 칸이 남는 한에 회수
def solution(cap, n, deliveries, pickups):
    ans = 0
    d = 0
    p = 0
    deliveries.reverse()
    pickups.reverse()

    for i in range(n):
        d += deliveries[i]
        p += pickups[i]
        while d > 0 or p > 0:
						# 둘중 하나가 음수가 된다고 break하지 않아도 된다
            d -= cap
            p -= cap
            ans += (n - i) * 2

    return ans
profile
멘티를 넘어 멘토가 되는 그날까지 파이팅
post-custom-banner

0개의 댓글