LV2 [KAKAO] 택배배달과 수거하기

 

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

 

풀이

푸는데만 4시간 가까이 걸렸다.

생각했던 풀이 같은 경우에는,

 

거리를 줄일려면 가장 먼 택배부터 배달해야한다고 생각했고, 가장 먼곳의 택배 배달을 끝내고, 여분이 남으면 그 앞에 배달위치까지 커버하는 방식으로 진행했다. (실질적으로 배달은 앞에서부터 되나, 뒤에서부터 내가 배달할 수 있는 양을 계산했다.)

 

수거또한 멀리서부터 할려고 했고, 가장 멀리있는 경우부터 수거하고, 공간이 남으면 앞의 수거목록까지 커버하는 방식으로 구현했다.

 

이 때 배달해야하는 곳이 가장 멀리있을수도 있고, 수거해야하는곳이 가장 멀리있을수도 있으니 둘 중 먼곳의 거리 * 2 를 답에 추가해주는 방식으로 진행했다. 그리고 중요한 포인트중 하나인데, 배달할때도 최대 cap개를 할 수 있고, 수거할 때도 최대 cap개를 항상 할 수 있다는것을 기억해야한다!

 

코드

def solution(cap, n, deliveries, pickups):
    # 총 배달해야하는 택배의 개수
    d_idx = n-1
    p_idx = n-1
    answer = 0

    # 마지막 택배 배달 위치를 찾는다.
    while deliveries[d_idx] == 0 and d_idx >= 0:
        d_idx -= 1

    while pickups[p_idx] == 0 and p_idx >= 0:
        p_idx -= 1

    while True:
        if d_idx < 0 and p_idx < 0:
            break
        # 배달할 택배가 더 뒤에 있다면
        if d_idx >= p_idx:
            # 가장 멀리가는곳을 답에 더해준다.
            answer += (d_idx+1) * 2
        # 만약 수거해야하는게 더 뒤에 있다면
        else:
            # 가장 멀리가는곳을 답에 더해준다.
            answer += (p_idx+1)*2

		# 최대개수를 들고간다.
        have = cap

        # 택배배달 프로세스
        while have != 0 and d_idx >= 0:
            # 내가 지니고 있는 택배개수보다 배달해야하는게 많을경우
            if deliveries[d_idx] > have:
                deliveries[d_idx] -= have
                have = 0

            # 그게 아니라면 모두 배달해준다.
            else:
                have -= deliveries[d_idx]
                # 그리고 앞으로 이동해준다.
                d_idx -= 1
                # 만약 앞이 배달할게 없을 수 있으니 검사해준다.
                while deliveries[d_idx] == 0 and d_idx >= 0:
                    d_idx -= 1

        have = 0
        # 택배수거 프로세스
        # 택배수거는 가장 먼곳에서부터 cap개수만큼 챙겨오면 된다.
        
        # 내가 가지고 있는게 최대개수보다 작으면
        while have < cap and p_idx >= 0:
            # 내가 지닌거 + 수거해야하는 양이 내가 최대로 들 수 있는 양 이상이라면,
            if pickups[p_idx] + have > cap:
                pickups[p_idx] -= (cap - have)
                have = cap
            # 그렇지 않다면
            else:
                # 모두 수거하고, 앞으로 이동해준다.
                have += pickups[p_idx]
                p_idx -= 1

                # 수거해야하는 위치로 까지 이동해준다.
                while pickups[p_idx] == 0 and p_idx >= 0:
                    p_idx -= 1

    return answer

 

후기

꽤나 오랜시간동안 풀었던 문제이다. 첫날에 3시간을 내리 박았다. 테스트케이스 일부는 맞는데, 이것저것 수정해봐도 답이 안나와서 다음날의 나에게 미뤘다. 그리고 다음날, 코드를 직접적으로 보지는 않고 카카오 공식 블로그에 올라온 풀이 방식을 참고했다. 

근데 풀이 방식이 내가 접근한 방식이랑 거의 똑같아서, 다시 코드를 천천히 살펴보기 시작했다. 자세히보니 조건문에 문제가 있었고, 한두줄 수정후에 맞출 수 있었다.

 

도움은 받았지만 결론적으로 내 코드에서 내가 문제를 찾아서 해결했다는게 뿌듯했고, 그 전날에는 보이지 않았던 문제가 다음날에는 보였던게 신기했다. 너무 매몰되었다 싶으면, 잠시 시간을 가지고 문제에 다시 접근해보자. 내가 찾지 못했던 문제를 발견할수도 있다.

 

https://tech.kakao.com/2023/01/25/2023-kakao-recruitment-round-1/

2023 카카오 신입 공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

 

* 그리고 카카오에서는 이 문제를 스택 방식으로 해결하라고 조언해줬는데, 뒤에서부터 참고해야하는 이 문제의 특성을 생각해보면 훨씬 더 깔끔한 접근법 같다.