[백준] 2512 예산 - Java

문제 - 예산

난이도 - 실버 2

 

https://www.acmicpc.net/problem/2512

2512번: 예산

 

---

문제 설명

 

 

 

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

 

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

 

예제 입력

4

120 110 140 150

485

 

예제 출력

 

-> 127

---

접근 방법

 

- 시간 제한이 1초라 반복문을 2개 이상으로 풀면 안될것 같다

- N은 int형, M은 long 으로 선언해줘야 할 것 같다 

- 우선 리스트에서 오름차순으로 정렬을 하고 상한가의 최대 치를 구해야 할 것 같다 -> 입력 받은 값중에서 제일 큰수

- 최소 0 최대는 입력 받은 값 중에서 제일 큰수로 잡고 그 안에서 상한가를 구해야 한다 하지만, 시간 제한이 1초라 그냥 탐색을 하면 안되고 이분 탐색을 해서 시간을 줄여야 할 것 같다

---

코드 작성

 

처음 코드 작성 (잘못 된 거)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        list.sort(Comparator.comparingInt(value -> value));

        long M = Long.parseLong(br.readLine());
        long max = list.get(list.size() - 1);
        long min = 0;
        long maxCount = 0;

        while (min <= max) {
            long mid = (max + min) / 2;
            long sum = 0;

            list.stream().forEach(value -> {
                sum += Math.min(value, mid);
            });


            if (sum > M) {
                max = mid - 1;
            } else {
                min = mid + 1;
                maxCount = Math.max(maxCount, mid);
            }
        }
        System.out.println(maxCount);
    }
}

 

이런식으로 while 문 안에 list를 stream으로 람다식을 이용해서 해봤는데 sum += Math.min(value, mid); 여기에서 에러가 난다

 

왜? 에러가 날까 

 

- 이유는 람다 표현식에서 사용되는 로컬 변수는 final 또는 effectively final이어야 한다. (effectively final 이란 한 번 값을 할당한 이후에 값을 변경하지 않는 변수를 의미)

 

왜? 람다 표현식 내부에서 사용되는 로컬 변수가 final 또는 effectively final이어야 할까? 

 

-> 1. 스레드 안정성 : 람다 표현식이 다른 스레드에서도 실행될 수 있다 즉, 여러 스레드 간에 안전하게 공유되어야 한다

이를 보장하기 위해서는 변경되지 않는 final 이나 스레드 간에 안전하게 값을 공유하고 변경할 수 있는 기능을 제공하는 atomic 변수를 사용할 수 있다

 

-> 2. 람다 캡처 변수의 수명 관리 : 람다 표현식은 자신이 참조하는 외부 변수의 값을 캡처합니다. 그러나 람다 표현식이 실행되는 동안 변수의 값을 변경할 수 없으므로(final 또는 effectively final), 변수의 수명이 람다 표현식의 수명과 일치하여 예기치 않은 동작을 방지한다

 

 

그러면?

 

그래서 atomic으로 변수형을 지정 하려다가 여기 코드에서는 병렬 처리를 하지 않기 때문에 일반적인 변수를 사용 할 것이다 그래서 람다 표현식이 아닌 for-each 문으로 처리 해주었다.....

 

 

코드 작성 (통과된 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        list.sort(Comparator.comparingInt(value -> value));

        long M = Long.parseLong(br.readLine());
        long max = list.get(list.size() - 1);
        long min = 0;
        long maxCount = 0;

        while (min <= max) {
            long mid = (max + min) / 2;
            long sum = 0;

            for (int money : list) {
                sum += Math.min(money, mid);
            }

            if (sum > M) {
                max = mid - 1;
            } else {
                min = mid + 1;
                maxCount = Math.max(maxCount, mid);
            }
        }

        System.out.println(maxCount);


    }


}

 

---

풀고 느낀점

1. 이 문제는 일반적인 이분 탐색 문제 인 것 같다 

2. stream 람다 표현식에서 로컬 변수를 위에 설명했던 것 처럼 해야 한다니 처음 알았다