[프로그래머스] 추석 트래픽 - Java

문제 : https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

풀이과정

첫 풀이부터 효율성을 염두에 두고 풀이를 진행하니 이래저래 결과 도출이 잘 되지 않아 가장 직관적이라고 생각되는 풀이 방법을 선택하였다.

 

풀이의 진행 과정은 다음과 같다.

 

먼저, 전체 트래픽 구간을 조사하여 최초 트래픽의 시작 시점부터 최종 트래픽의 종료 시점 까지를 확인한다. 그리고 이 범위를 int array로 선언한다. 이 때, 각 원소는 이 구간 내에서의 1 ms동안의 시간을 의미한다. 이를 그림으로 살펴보면 다음과 같은 상태이다.

주어진 전체 트래픽 구간의 길이에 맞는 int array 선언

 

다음으로 , 주어진 각 트래픽에 대해서 해당 트래픽의 구간 범위에 맞는 원소마다 +1씩 수행해준다. 즉, 위 배열에서 각 원소의 값은 그 시간에 들어온 트래픽의 수에 해당한다. 그림으로 보면 아래와 같이 진행된다.

트래픽 처리량 정보 업데이트 과정

그리고 마지막으로, 위 그림처럼 각 트래픽 정보가 배열에 모두 업데이트 된 다음 전체 배열을 순회하면서 최댓값을 찾으면 그 값이 바로 문제에서 요구하는 초당 최대 트래픽 처리량이 된다. 위 그림의 예시에서는 앞에서부터 7번째 칸 (7ms) 시점에서의 원소값이 3으로, Traffic 2, 3, 4가 겹쳐 초당 최대 트래픽 처리량이 3이 알 수 있다.

 

소스코드

import java.util.*;

class Solution{
    public int solution(String[] lines) {
        // request time 순으로 정렬하기 위해 Priority Queue 사용
        PriorityQueue<TrafficTime> pq = new PriorityQueue<>();
        int latestTime = Integer.MIN_VALUE;

        // 가장 마지막으로 response가 일어나는 시간 찾기 → 배열을 만들기 위해 사용
        for (String line : lines) {
            TrafficTime trafficTime = new TrafficTime(line);
            int responseTime = trafficTime.getResponseTime();
            if (latestTime < responseTime) {
                latestTime = responseTime;
            }

            pq.offer(trafficTime);
        }

        // 1. 가장 이른 request time 부터 가장 늦은 response time + 1초 까지를 배열로 표현한다.
        // 편의상 가장 이른 시간이 index 0을 갖도록 설정
        int earliestTime = pq.peek().getRequestTime();
        latestTime -= earliestTime;
        int[] counter = new int[latestTime + 1000];

        // 2. 각 traffic이 처리되는 것으로 잡히는 구간의 배열 원소값을 +1 하기
        while (!pq.isEmpty()) {
            TrafficTime trafficTime = pq.poll();
            int requestTime = trafficTime.getRequestTime();
            int responseTime = trafficTime.getResponseTime();

            for (int i = requestTime - earliestTime; i < responseTime - earliestTime + 1000; i++) {
                counter[i]++;
            }
        }

        // 3. 배열의 최댓값 찾기
        int answer = Integer.MIN_VALUE;
        for (int count : counter) {
            if (answer < count) {
                answer = count;
            }
        }

        return answer;
    }
}

class TrafficTime implements Comparable<TrafficTime> {
    // milliseconds 단위를 기준으로 계산 수행
    private final int requestTime;
    private final int responseTime;

    TrafficTime(String trafficInfo) {
        String[] info = trafficInfo.split(" ");
        String timeInfo = info[1];

        int time = 0;

        time += (int)(Double.parseDouble(timeInfo.substring(0, 2)) * 3600 * 1000); // hours
        time += (int)(Double.parseDouble(timeInfo.substring(3, 5)) * 60 * 1000); // minutes
        time += (int)(Double.parseDouble(timeInfo.substring(6,12)) * 1000); // seconds

        this.responseTime = time;
        // 처리시간은 시작시간과 끝시간을 포함하므로 request time = response time - 처리시간 + 1 millisecond
        this.requestTime = time - (int)(Double.parseDouble(info[2].substring(0, info[2].length() - 1)) * 1000) + 1;
    }

    public int getRequestTime() {
        return this.requestTime;
    }

    public int getResponseTime() {
        return this.responseTime;
    }

    // Request time 을 기준으로 오름차순 정렬하도록 설정
    @Override
    public int compareTo(TrafficTime o) {
        return (int)(this.getRequestTime() - o.getRequestTime());
    }
}