[백준] 2836번. 수상 택시(JAVA)

문제

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

---

풀이(40분)

import java.io.*;
import java.util.*;

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

        long N = Long.parseLong(st.nextToken());
        long M = Long.parseLong(st.nextToken());
        long totalDistance = M;

        List<Taxi> reverse = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            long start = Long.parseLong(st.nextToken());
            long end = Long.parseLong(st.nextToken());

            if (start > end) {
                reverse.add(new Taxi(start, end));
            }
        }

        if (reverse.isEmpty()) {
            System.out.println(totalDistance);
            return;
        }

        Collections.sort(reverse);

        long minEnd = reverse.get(0).end;
        long maxStart = reverse.get(0).start;

        for (int i = 1; i < reverse.size(); i++) {
            Taxi trip = reverse.get(i);

            if (trip.end <= maxStart) {
                maxStart = Math.max(maxStart, trip.start);
            } else {
                totalDistance += 2 * (maxStart - minEnd);
                minEnd = trip.end;
                maxStart = trip.start;
            }
        }

        totalDistance += 2 * (maxStart - minEnd);
        System.out.println(totalDistance);
    }

    static class Taxi implements Comparable<Taxi> {
        long start;
        long end;

        public Taxi(long start, long end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Taxi o) {
            int endComparisonResult = Long.compare(this.end, o.end);
            
            if (endComparisonResult != 0) {
                return endComparisonResult;
            } else {
                return Long.compare(this.start, o.start);
            }
        }

    }
}

---

문제 풀이 전략

 

문제 해결 아이디어를 잡는데 오래 걸렸던 문제이다.

 

첫 번째로 떠오른 아이디어는 먼저 정방향 -> 도착지가 출발지보다 먼 경우는 고려할 필요가 없다.

-> 내려야하는 순서가 존재하는 것이 아니기에 어차피 0~M까지 모두 운행하는 특성상 고려 대상이 아니다.

 

두 번째 아이디어는 이 전 최대 출발지보다 도착지가 더 먼 경우에 대해서만 계산을 한 뒤에 이를 고려하면 된다는 것이다.

생각보다 직접 공책에 써가며 정리해야 하는 문제라고 느껴졌다. 

https://nahwasa.com/entry/%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-2836-%EC%88%98%EC%83%81-%ED%83%9D%EC%8B%9C-java

[자바] 백준 2836 - 수상 택시 (java)

최종적으로 문제를 해결한 뒤에 다른 분들의 풀이를 참고하며 본 글이다. 정리를 되게 잘 해주신 것 같으니 아이디어를 참고하자!

 

마지막으로 중요했던 것은 Long.compare 문법이다. 사실 int 형만 다루다 보니 평소에 return을 this.start - o.start 이런 식으로 하는 경우가 많았는데 큰 값을 비교해야 한다면 연습할 필요가 있다고 느꼈다!