[자바/해시맵] 코드트리 IM: 낮은 지점들 - int의 범위

point of failure

주어지는 숫자의 범위가 -10억부터 +10억까지인데, 나는 출력하기 위한 값을 저장하는 변수 ans를 int 타입으로 선언하였다.

 

analysis

로직 자체는 어렵지 않은 문제였다. 하지만 컴퓨터는 항상 타입별로 표현할 수 있는 숫자의 크기가 다르단 것을 명심해야 한다. 현재 주어질 수 있는 x, y의 범위가 10억까지인데, int는 약 -20억(-2*10^9)부터 +20억(+2*10^9)까지 표현이 가능하다. 그렇다면 단발적으로 x, y 좌표를 나타낼 순 있지만, 3개의 y 좌표를 더한 값을 나타내려 하는 순간 overflow가 발생한다. 따라서 정답을 담아야 하는 변수는 long으로 나타내야 한다.

 

그렇게 하면 n이 1000이라 하더라도, 즉 10억인 y가 1000개 있다 하더라도 10^12승 정도의 숫자 크기가 나오게 되는데 long은 -9*10^18 ~ +9*10^18 정도로, int 범위의 제곱 이상의 크기이기 때문에 무리없이 정답을 표현할 수 있다.

 

algorithm

저장한 숫자를 계속 접근하여 값을 갱신해주는 패턴이므로 HashMap을 이용하여 풀어낼 수 있다.

 

logic

public class 낮은_지점들 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int x, y;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            if (map.containsKey(x)) {
                replaceSmallerValue(x, y, map);
            } else {
                map.put(x, y);
            }
        }
        long ans = 0;
        for (Integer value : map.values()) {
            ans += value;
        }
        System.out.println(ans);
    }

    private static void replaceSmallerValue(int x, int y, Map<Integer, Integer> map) {
        if (y < map.get(x)) {
            map.replace(x, y);
        }
    }
}