그리디

프로그래머스 2023 KAKAO BLIND RECRUITMENT Level 2 문제 택배 배달과 수거하기를 java를 이용하여 풀어보았다.
탐욕법으로 푸는 문제다. 이제 죄다 탐욕법만 나오니 힘들다.

문제 링크 첨부한다.
https://school.programmers.co.kr/learn/courses/30/lessons/150369

---

규칙 만들기

내가 풀은 풀이는 배열을 뒤에서부터 탐색하며 배달과 픽업을 별개로 두어 각각의 누적 개수를 구하는 과정에서 다시 돌아와야 할 지점을 체크해주는 방식으로 풀었다.
좀더 풀어 설명하자면, 배달의 경우에 5,3,2 지점으로 돌아가야 하고 픽업의 경우에 4,1 지점으로 돌아가야 한다고 가정해보자.

배열을 뒤에서부터 탐색했으므로 깃발이 꽂힌 지점이 큰 숫자부터 들어와 있는 것이라 생각하면 된다. 나는 저 지점들을 각각 큐에 넣었다. 두 큐 중 작은 큐의 길이가 2 이므로 2번을 poll() 해서 더 큰 지점으로 돌아가면 되는 것이다.

1. 먼저 5와 4가 각각 튀어나올테고, 더 먼 지점인 5까지 돌아가야 한다는 것이다.
2. 다음으로 3과 4가 튀어나올테고, 더 먼 지점인 4까지 돌아가야 하는 것이다.
3. 배달은 여전히 2로 돌아가야 하고, 픽업은 이미 다 끝났기 때문에 마지막으로 2로 돌아갔다 오면 된다.

모두 왕복 기준이기 때문에 1,2,3 에서 나온 지점들을 모두 더해주고 2를 곱해주면 되는 식이다.

solution 코드는 다음과 같다.

long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        if(deliveries[n-1]!=0 || pickups[n-1]!=0)   answer += n+n;
        Queue<Integer> delQ = new LinkedList<>();
        Queue<Integer> pickQ = new LinkedList<>();

        getStopPoint(cap, n, deliveries, delQ);
        getStopPoint(cap, n, pickups, pickQ);

        int len = Math.min(delQ.size(), pickQ.size());

        for(int i=0; i<len; i++){
            int del = delQ.poll();
            int pick = pickQ.poll();
            int max = Math.max(del, pick);
            answer += max + max;
        }

        if(!delQ.isEmpty()){
            while(!delQ.isEmpty()){
                int tmp = delQ.poll();
                answer += tmp + tmp;
            }
        }

        if(!pickQ.isEmpty()){
            while(!pickQ.isEmpty()){
                int tmp = pickQ.poll();
                answer += tmp + tmp;
            }
        }

        return answer;
    }

static void getStopPoint(int cap, int n, int[] ary, Queue<Integer> q) {
        int cnt = 0;

        for(int i=n-1; i>=0; i--){
            if(ary[i]==0)   continue;
            if(cnt==cap){
                q.add(i+1);
                cnt = 0;
            }

            if(cnt+ary[i]<cap){
                cnt += ary[i];
                ary[i] = 0;
            }
            else if(cnt+ary[i]>cap){
                ary[i] -= (cap - cnt);
                q.add(i+1);
                cnt = 0;
                i++;
            }
            else{
                cnt = cap;
                ary[i] = 0;
            }
        }
    }

---

이렇게 풀면 틀린다!

사실 위에처럼 풀어서 20개의 테스트케이스는 모두 통과했다. 하지만... 테스트케이스 20개에 위 코드에 따른 예외 경우가 포함되어 있지 않다. 출제진이 실수한 건지 뭔지 모르겠지만 어쨌든 내가 짠 로직에 허점이 있다는 것이다.

int cap = 2, int n = 2
int[] deliveries = {1,0}
int[] pickups = {1,0}
와 같은 경우는 1까지 왔다갔다 해야하니까 결과로 2가 나와야 하지만 위 코드로 돌리면 0이 나온다. 하지만 테스트케이스에는 위와 같은 경우가 없나보다.

내 코드에서 조금 더 손을 봐서 예외 경우를 통과시켜보려 했지만 좀처럼 잘 되지 않았다.

---

틀 밖에서 생각하기

결국 위 예외사항을 통과시키고 싶어 다른 사람들의 풀이를 참고했다. 가장 인상적인 풀이를 만나게 됐는데 나와 다른 점은 다음과 같았다.

물건 개수를 딱 맞춰서 계산할 필요없이 내가 어디를 몇 번 가야하는지에만 신경 썼다는 점이 달랐다. 무슨 말이냐하면, 실제로 남은 배달 개수는 1개일지라도 5개를 배달한다 치면 어쨌든 1개는 커버가 된다는 발상이다. 맨 처음에 짧은 두 줄 설명으로만 자신의 코드를 설명해두셨길래 뭔 말인가 이해하지 못했는데 직접 코드를 보며 테스트 케이스들을 적용해보니 이해가 됐다.

코드는 다음과 같았다.

long solution2(int cap, int n , int[] deliveries, int[] pickups){
        long answer = 0;

        int give = 0; // 배달
        int take = 0; // 픽업
        for(int i=n-1 ;i>=0;--i) {
            if(deliveries[i]!=0 || pickups[i]!=0) {
                int cnt=0;
                while(give < deliveries[i] || take< pickups[i])
                {
                    ++cnt;
                    give+=cap;
                    take+=cap;
                }
                give -= deliveries[i];
                take -=  pickups[i];
                answer = answer + ((long) (i + 1) *cnt*2); // 특정 지점을 몇 번 찍어야하는가
            }
        }
        return answer;
    }

---

마치며

이런 인간들 풀이 보면 힘 빠진다. 젠장
너무 숫자 하나 하나에 집착하기보다도 문제를 어떻게 해결하는가에 더 초점을 맞춰야 하는데 막상 내가 생각해낸 풀이에 몰입하는 순간 내 머리 한계의 틀 안에 갇히는 기분이다. 남의 풀이 참고하는 걸 무조건 지양하기보다도 어떻게들 문제를 해결하는가를 보며 더 많은 관점들을 배워야겠다.

평소에 내가 풀고 나서 남의 풀이 보면 '아 시험장에서 난 저렇게 어차피 못 풀어' 하는 마음으로 넘기기 일쑤였는데 이제부터는 좀 더 깊이 고민하며 다른 사람들의 풀이를 깊이 있게 이해하려는 노력도 병행해야겠다.