[2018 카카오 기출][Java] 추석 트래픽

문제 링크

2018 KaKao Blind Recruiment - 추석 트래픽

문제 분석

2016-09-15 hh:mm:ss.sss 포맷의 문자열과 처리 시간이 로그 데이터 형식으로
주어지는 문제입니다. 처리시간은 최소 0.001s 최대 3s입니다.

로그에 주어진 시간은 완료 시간이므로, 09-14일의 로그데이터가 날아올 수 있으므로
이를 고려해야합니다.

또한 ms(밀리세컨드) 형식으로 데이터가 주어지기 때문에 소수점을 고려하여
이를 정수형으로 바꾸는 과정이 필요합니다

이런 조건들을 고려하여 임의의 시간을 기준으로 1000ms동안 완료를 고려하지 않는
최대 처리량을 찾아야합니다.

풀이 코드

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(String[] lines) {
        int answer = 0;
        
        ArrayList<Timeset> setList = new ArrayList<>();
        
        for(String log : lines) {
            String[] tokens = log.split(" ");
            String[] timeTokens = tokens[1].split(":");
            
            // Processing Time (ms)
            double pTimeF = Double.parseDouble(tokens[2].substring(0, tokens[2].length() - 1));
            int pTime = (int) (pTimeF * 1000.0);
            
            // endTime (ms)
            int endTime = Integer.parseInt(timeTokens[0]) * 60 * 60 * 1000;
            endTime += Integer.parseInt(timeTokens[1]) * 60 * 1000;
            endTime += (int) (Double.parseDouble(timeTokens[2]) * 1000.0);
            
            // startTime (ms)
            int startTime = endTime - pTime + 1;
            
            setList.add(new Timeset(startTime, endTime));
        }
        Collections.sort(setList);
        
        int tempTime = Integer.MIN_VALUE;
        PriorityQueue<Timeset> queue = new PriorityQueue<>();
        for(Timeset set : setList) {
            if(set.end > tempTime + 999) {
                if(set.start > tempTime + 999) {
                    answer = Math.max(answer, queue.size());
                    while(!queue.isEmpty()) {
                        if(set.start > queue.peek().start + 999) {
                            Timeset ts = queue.poll();
                            if(ts.end > ts.start) {
                                queue.add(new Timeset(ts.end, ts.end));
                            }
                        }
                        else {
                            tempTime = queue.peek().start;
                            break;
                        }
                    }
                }
            }
            queue.add(new Timeset(set.start, set.end));
        }
        
        answer = Math.max(answer, queue.size());
        
        return answer;
    }
    
    public class Timeset implements Comparable<Timeset>{
        public int start, end;
        public Timeset(int start, int end) {
            this.start = start;
            this.end = end;
        }
        
        @Override
        public int compareTo(Timeset obj) {
            Integer num1 = new Integer(this.start);
            Integer num2 = new Integer(obj.start);
            return num1.compareTo(num2);
        }
    }
}

풀이 과정

코드와 같이 풀이를 진행하겠습니다.

먼저 풀이에서 사용할 Timeset Class입니다. Comparable을 implements 하여
비교 연산이 가능하도록 Override합니다. Timeset은 로그의 처리 시작 시간과
종료 시간을 필드로 가지며, 비교 연산에서는 start를 기준으로 정렬됩니다.

문자열을 처리하는 부분입니다. 완전 순회를 시행하므로 Stream을 사용하며
먼저 2016-09-15 hh:mm:ss.sss x.xxs 형식으로 된 log를 공백을 기준으로 파싱합니다.
그러면 [0]에는 날짜, [1]에는 시간, [2]에는 처리시간이 들어갑니다.

pTimeF를 선언하여 [2]에 담긴 토큰에서 's' 문자를 제거한 후 1000을 곱하여
처리 시간을 int형으로 변환합니다. 이런 과정을 거치면 0.145s와 같은 초 기준 값이
밀리초 값으로 바뀌게 됩니다.

이후 종료 시간을 나타내는 hh:mm:ss.sss 부분도 밀리초 값으로 변환해줍니다.
hh에는 3600 x 1000, mm에는 60 x 1000, ss.sss에는 1000을 곱해 밀리초 범위로
변환합니다. 23:59:59.999도 int형 범위를 넘지 않으므로(int 범위는 약 21억)
오버플로우로부터 안전합니다.

이후 종료 시간에서 처리 시간을 빼고 1을 더한다면(시작, 종료시간을 포함하므로 1을 뺌)
시작시간을 구할 수 있습니다. 14일로부터 넘어온 로그는 음수값을 가지게 됩니다.
하지만 따로 처리해줄 필요는 없습니다.

모든 로그를 밀리초로값으로 변환한 후 Collections.sort를 통하여
Timeset들이 담긴 List를 시작시간 기준으로 오름차순 정렬해줍니다.

시작시간으로 정렬하는 이유

이 문제의 로그데이터는 이미 종료시간을 기준으로 정렬되어 있습니다.
제가 여기서 다시 시작시간으로 정렬한 이유는 다음과 같은 경우 때문이었습니다.

위 3개의 로그데이터는 종료시간(막대의 오른쪽 끝)을 기준으로 정렬되어 있습니다.
만약 로그를 순서대로 탐색한다면, 1번 막대는 3번 막대의 존재를 알 수 없게 됩니다.

물론 종료시간을 기준으로도 해결할 수 있는 방법이 있을 수 있으나 저는
종료시간을 기준으로 사용하였을 때 3번과 18번 케이스에서 계속 실패를 해서
직관적 편의를 위하여 시작시간으로 정렬하였습니다...

PriorityQueue를 사용한 풀이

첫 tempTime은 0으로 초기화하지 않고 Integer.MIN_VALUE로 초기화합니다.
0으로 초기화하게되면 14일부터 날아온, 현재 음수를 가지는 로그들을
제대로 처리할 수 없기때문에 MIN_VALUE로 초기값을 설정합니다.

아까와 마찬가지로 stream을 통해 Timeset들을 탐색하는데
set.end가 tempTime + 999 인 경우부터 탐색을 하기 시작합니다.

tempTime을 시작점으로 설정했으니 tempTime을 기준으로 +999인 값을 잡습니다.
이후 두 번째 log는, end값이 tempTime + 999보다 작으므로
queue에 add합니다.

이후 다음 log는 end값은 tempTime+999보다 크나, start값이 tempTime+999보다
작으므로 queue에 add합니다.

이제 다음 log값은 tempTime+999보다 start, end값이 모두 큰 경우입니다.
해당 경우는 어떻게 처리할까요?

먼저 똑같이 tempTime을 새로운 4번째 로그의 시작점으로 잡습니다.
그 이후 queue에 존재하는 로그값들을 poll로 꺼내옵니다.

만약 꺼내온 log의 end값이 바뀐 tempTime+999 범위에 들어올 경우,
새로운 log 객체를 (end, end)값으로 생성합니다.

이 방법을 사용하면 start, end 지점을 모두 검사하면서 추가적인
큰 사이즈의 밀리세컨드 배열을 생성하지 않고 로그들을 처리할 수 있습니다.

채점 결과 및 정리

사실 지난번에 풀었던 단속 카메라와 비슷한 그리디 형식의 알고리즘과,
문자열 처리를 결합한 형태의 문제였던 것 같습니다.

처음에 기본적으로 정렬된 종료 시점을 기준으로 문제를 해결하려고 하다
3번과 18번 두 개의 테스트 케이스가 계속 실패하여 시작 시간을 기준으로
재정렬하여 풀이에 성공했습니다.

2018년 카카오 코딩테스트 중 가장 어려운 문제였던 만큼 풀이에 많은 시간이
소모된 문제인 것 같습니다