Today's Algorithm(2019-02-14)

며칠 전에 푼 문제인데 최근에 좀 바빠서 바로 정리하지 못했네요. 빠르게 정리해볼게요!

 

추석 트래픽

이번에 푼 문제는 문제 자체를 이해하는 것이 참 힘들었습니다. 문제를 제대로 이해하는 것에서부터 해결방법을 고려해야하는데 문제 이해에서만 20~30분이 걸린 것이죠.

 

이 문제에서 날짜 데이터를 처음엔 Date 를 이용해서 푸려고 했습니다. 하지만 이 값을 이용해야하는데 Date 타입으로는 어떻게 해야할지 잘 모르겠더라구요. 그래서 getTime() 을 이용하여 다시 ms 단위로 바꾸었습니다. 결론적으로 이렇게 푸는 것이 더 낫다는 생각이 들었습니다. 그 이유는 초가 소수점 3자리까지 표현되기 때문에 ms로 나타내는 것이 소수점 계산을 하지 않아도 된다는 점에서 유리하였기 때문입니다.

 

다만 문제를 풀면서 주의할 점은 다음과 같습니다.

• 처음시간, 끝시간을 모두 포함하기 때문에 시작 시간을 구하려면 (끝시간 - 처리시간 + 00.001)이 필요합니다.
• 포함하는지 여부를 구하는 구간을 설정할 때 위와 같은 이유로 처음 시간이 s라면 끝시간은 s + 999(ms) 입니다. 1000(ms)가 아니라는 것을 명심해야 합니다.

class Solution {
    public int solution(String[] lines) throws ParseException {
        int answer = 0;
        List<Process> list = split(lines);
        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            long endTime = list.get(i).endTime;
            int temp = 0;
            for (Process process : list) {
                if(process.include(endTime)) temp++;
            }
            answer = Math.max(answer, temp);
        }

        return answer;
    }

    List<Process> split(String[] lines) throws ParseException {
        SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        List<Process> list = new ArrayList<>();
        for (String line : lines) {
            String[] splittedLine = line.split(" ");
            long endTime = dateFormat.parse(splittedLine[0] + " " + splittedLine[1]).getTime();
            long startTime = endTime - (long)(Double.parseDouble(splittedLine[2].substring(0, splittedLine[2].length() - 1)) * 1000) + 1;
            list.add(new Process(startTime, endTime));
        }
        return list;
    }
}

class Process implements Comparable<Process>{
    long startTime;
    long endTime;

    public Process(long startTime, long endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    public boolean include(long target) {
        long targetStart = target;
        long targetEnd = target + 999;

        return targetStart <= endTime && targetEnd >= startTime;
    }
    
    @Override
    public int compareTo(Process o) {
        return (int)(this.startTime - o.startTime);
    }
}

 

 

셔틀버스

그렇게 어려운 문제가 아니었지만 제가 부족하여 생긴 문제로 인해 어려움을 겪게 되었습니다. 그 부분 위주로 정리할게요.

• 먼저 LocalTime 을 사용하게 되면서 생긴 문제가 있습니다. 그건 24:00 일때 문제인데 LocalTime 은 24:00가 아니라 00:00로 계산되기 때문에 이 경우 런타임 에러가 발생하게 됩니다.
• 좌석이 하나도 남아있지 않을 때 가장 마지막 승객의 시간을 기준으로 -1분을 하는 방법으로 계산하였기 떄문에 마지막 승객의 정보를 가지고 있는 변수가 있습니다. 근데 문제는 마지막 승객이 셔틀을 못타는 경우가 있는데 그런 경우에 엉뚱하게 못타는 승객 시간정보를 가지고 있어서 문제가 발생했습니다.
• while문에서 Queue 의 특정 정보를 뽑아낼 때 경우가 있었습니다. 처음에는 일단 while문 안에 들어오게 하고 거기에서 if문을 통해 별도로 처리했었는데 그렇게 하다보니 코드의 복잡도가 증가하였습니다. 이 경우 while문 조건에서 Queue 의 peek() 메서드를 통해 손쉽게 해결할 수 있었습니다.

 

이 문제는 추석 트래픽과 비교도 안되게 위 두 가지 문제로 오랜 시간이 소요되었습니다.

package p17678;

import java.time.LocalTime;
import java.time.format.DateTimeFormatter;
import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        Queue<LocalTime> queue = init(timetable);

        LocalTime shuttleTime = LocalTime.of(9, 0);
        LocalTime temp = queue.peek();
        int remainingSeat = m;

        for (int i = 0; i < n; i++) {
            while (!queue.isEmpty() && remainingSeat > 0 && shuttleTime.compareTo(queue.peek()) >= 0) {
                temp = queue.poll();
                remainingSeat--;
            }

            if (i + 1 < n) {  // 버스가 더 남아있다
                shuttleTime = shuttleTime.plusMinutes(t);
                remainingSeat = m;
            }
        }

        if (remainingSeat > 0) return shuttleTime.toString();
        else return temp.minusMinutes(1).toString();
    }

    Queue<LocalTime> init(String[] timetable) {
        DateTimeFormatter TIMEFORMAT = DateTimeFormatter.ofPattern("HH:mm");
        Queue<LocalTime> timeList = new PriorityQueue<>();
        for (String s : timetable) {
            if(s.equals("24:00")) s = "23:59";
            LocalTime time = LocalTime.parse(s, TIMEFORMAT);
            timeList.offer(time);
        }
        return timeList;
    }
}