프로그래머스: 추석 트래픽 [JAVA]

문제 설명

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

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

풀이

 해당 문제는 완전 탐색으로 풀었는데, 탐색의 기준을 무엇으로 잡느냐가 중요하다. 만약 요청들의 단위가 1ms라고 무작정 총 시작시간과 완료시간 사이에 대해 1ms 단위로 탐색을 시작하면 시간 초과가 발생하게 된다. 그러기에 대부분의 범위를 잡을 때 초당 최대량이 최대가 되는 부분은 어떠한 요청이 들어오거나 끝나는 시점에서 시작되기 때문에, 해당 부분들만을 기준으로 탐색을 진행하면 통과가 가능하다.

 우선 입력받은 배열들을 파싱한 다음, 응답 완료 시간을 구하고 처리 시간을 통해 시작 시간 또한 구한다. 이 경우 처음에는 LocalDateTime 타입을 사용하려했는데, 밀리초 단위 계산을 하는데 Date 타입이 더 쉬워 Date 타입으로 각각 시간을 계산해 저장한다.

 이후에는 각 요청들의 처음과 끝 시간에서 1초간을 기준으로 계산을 진행한다. 다른 요청들의 요청 시작 또는 응답 완료 시간이 기준 사이에 있는지, 또는 요청의 시작 또는 완료시간 사이에 기준이 포함되어 있는지를 통해 이를 만족하면 답에 추가한다. 이후 기존 있는 답과 현재의 답안을 비교해 더 큰 값으로 변경하면 된다.

 

class Solution {
        public int solution(String[] lines) throws Exception {
            int answer = 0;
            SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss.SSS");//문자열 처리용 포맷

            Date ends[] = new Date[lines.length];//응답 완료 시간
            Date starts[] = new Date[lines.length];//응답 시작 시간

            for (int i = 0; i < lines.length; i++) {
                String word[] = lines[i].split(" ");//일자, 시간, 처리시간
                //처리시간 계산
                String processingTime = word[2].substring(0, word[2].length() - 1);
                long milliSec = (long) (Float.parseFloat(processingTime) * 1000);
                //응답 완료, 시작 시간 계산
                Date endTime = format.parse(word[1]);
                Date startTime = new Date(endTime.getTime() - milliSec + 1);

                ends[i] = endTime;
                starts[i] = startTime;
            }

            for (int i = 0; i < ends.length; i++) {//각 처리 시간에 대해 시작, 완료 시간에서 계산
                int throughput1 = 0, throughput2 = 0;
                for (int j = 0; j < ends.length; j++) {
                    if ((starts[j].getTime() - ends[i].getTime() < 1000 && starts[j].getTime() - ends[i].getTime() >= 0)
                            || (ends[j].getTime() - ends[i].getTime() < 1000 && ends[j].getTime() - ends[i].getTime() >= 0)
                            || (starts[j].getTime() <= ends[i].getTime() && ends[j].getTime() >= ends[i].getTime()))
                        throughput1++;

                    if ((starts[j].getTime() - starts[i].getTime() < 1000 && starts[j].getTime() - starts[i].getTime() >= 0)
                            || (ends[j].getTime() - starts[i].getTime() < 1000 && ends[j].getTime() - starts[i].getTime() >= 0)
                            || (starts[j].getTime() <= starts[i].getTime() && ends[j].getTime() >= starts[i].getTime()))
                        throughput2++;
                }
                answer = Math.max(answer, throughput1);
                answer = Math.max(answer, throughput2);
            }

            return answer;
        }

결과