Q 22988 재활용 캠페인

💡 문제 요약 및 분석

빈 헤어 에센스 용기를 가져다 주면 새로운 용기에 헤어 에센스를 채워주는 가게가 있다. (에센스를 채워주는 기준은 아래와 같다) 히나가 N개의 용기를 가져갈 때 꽉 찬 헤어 에센스 용기를 최대 몇 개 만들 수 있는지 출력하자.

Aml, Bml 용량이 남은 헤어 에센스 용기 두 개를 반납하면 A + B + X/2 만큼 새로운 용기에 헤어 에센스를 채워준다.
새로운 용기에 담는 헤어 에센스는 총 용량 Xml 를 초과하지 않는다.

💡 알고리즘 설계

✅ 핵심 아이디어 : 최대한 남은 용량이 적은 것들끼리 모아서 반납하는 것이 이득이다. 배열을 정렬한 후 계산하자.

입력
- 표준입력으로 int N, int X 생성.
- 표준입력을 받아 List bottles 배열 생성. 입력값 == X 인 경우 count++ 하고 리스트에 넣지 않는다.
- 해당 배열을 오름차순 정렬한다.
연산
- left = 0, right = 1
- while(right < bottles.size) 까지 반복하면서 아래 로직을 수행한다.
- int recycle = Math.min(bottles.get(left) + bottles.get(right) + X/2, X)
- recycle == X : count++
- recycle < M : recycle 값을 bottles 리스트의 마지막에 추가
- left += 2, right += 2;
출력
- count 변수를 출력한다.

💡 코드

import java.util.*;

public class Main {

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int N = read();
        int X = read();
        List<Integer> bottles = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < N; i++) {
            int input = read();
            if (input == X) {
                count++;
            } else {
                bottles.add(input);
            }
        }
        Collections.sort(bottles);

        int left = 0, right = 1;
        while (right < bottles.size()) {
            int recycle = Math.min(bottles.get(left) + bottles.get(right) + X/2, X);
            if (recycle == X) {
                count++;
            } else if (recycle < X) {
                bottles.add(recycle);
            }
            left += 2;
            right += 2;
        }
        System.out.println(count);
    }

}

💡 틀린 부분 분석

계속 수정해봐도 틀려서 로직 자체의 문제가 아닐까 의심하게 되었다. 그래서 정답을 찾아보니 애초에 나의 접근 방식이 틀렸다는 것을 알게 되었다. 이 문제는 투 포인터를 활용해서 풀어낼 수 있다. 일단 최적의 답을 구하기 위한 조건은 다음과 같다.

남은 용량이 많은 용기와 적은 용기를 합치는 것이 좋다. 왜냐하면 기본적으로 X/2 용량을 확보한 상태에서 두 용기의 남은 용량을 더해주기 때문에, 남은 X/2 용량을 한 번에 채울 수 있다면 최적의 조합일 것이다. 이 경우 우리가 생각해야할 min 값은 다음과 같다.
- X 가 홀수인 경우 : min == X/2 + 1 (주어지는 수가 정수이기 때문에 나누면 0.5가 남을 것이다. 이를 채워주기 위해 +1 한다.)
- X 가 짝수인 경우 : min == X/2
헤어 에센스 용기가 3개 있으면 가득 찬 용기 하나를 얻을 수 있다. 왜냐하면 두 개를 합치면 X/2 용량이 생기고, 세 번째 용기의 남은 양이 어떻든 X/2 용기와 합치면 다시 X/2 용량이 생기기 때문에 (X/2) + (X/2) = X 로 온전한 한 병이 된다.
애초에 X 만큼의 용량을 가진 병은 이미 온전한 한 병이므로 다른 병과 합치지 않아도 된다.

💡 알고리즘 재설계 및 정답 코드

표준입력으로 입력받은 배열을 오름차순으로 정렬한다.
left[0], right[length - 1] 에서 출발한다.
다음과 같은 조건에 따라 포인터를 움직인다. L + R >= min : count++, L++, R-- L + R < min : L++
두 포인터가 같은 원소를 가리킬 때 종료된다.
남은 병의 개수 / 3 으로 나눈 값을 count 변수에 추가한다. (왜냐하면 용기 3개만 있으면 용량과 관계없이 온전한 한 병이 만들어지므로)
count 변수를 출력한다.

import java.util.*;

public class Main {

    static long read() throws Exception {
        long c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int N = (int)read();
        long X = read();
        long min = (X + 1) / 2;

        long[] bottles = new long[N];
        int bottleCount = 0;
        int count = 0;
        
        for (int i = 0; i < N; i++) {
            long input = read();
            if (input >= X) {
                count++;
            } else {
                bottles[bottleCount++] = input;
            }
        }
        
        Arrays.sort(bottles, 0, bottleCount);

        int left = 0;
        int right = bottleCount - 1;
        int remain = bottleCount;

        while (left < right) {
            long sum = bottles[left] + bottles[right];
            if (sum >= min) {
                count++;
                left++;
                right--;
                remain -= 2;
            } else {
                left++;
            }
        }

        count += remain / 3;
        System.out.println(count);
    }
}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n)	O(n)

💡 느낀점 및 기억할 정보

메모리 사용량 주의 !!

분명 로직은 맞는데 계속 틀렸다고 해서 설마 메모리가 부족한가…? 싶어서 List –> 배열 로 바꿔보았더니 성공했다. 문제에서 주어진 메모리가 1024mb 로 이 정도면 넉넉하다고 생각했는데 설마 이게 원인일 줄은…