카카오 신입공채 1차 코딩테스트 문제7 추석트래픽 JAVA 예제

카카오톡 1차 코딩 테스트 문제7 추석트래픽 JAVA 예제

카카오 신입공채 1차 코딩테스트 문제7 추석트래픽 JAVA 예제

---

문제설명

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

입력형식

• solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
• 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
• 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
• 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 “2016년 9월 15일 오전 3시 10분 33.010초”부터 “2016년 9월 15일 오전 3시 10분 33.020초”까지 “0.011초” 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
• 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
• lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

입출력 예제

입력: [ “2016-09-15 01:00:04.001 2.0s”, “2016-09-15 01:00:07.000 2s” ]

출력: 1

입력: [ “2016-09-15 01:00:04.002 2.0s”, “2016-09-15 01:00:07.000 2s” ]

출력: 2

입력: [ “2016-09-15 20:59:57.421 0.351s”, “2016-09-15 20:59:58.233 1.181s”, “2016-09-15 20:59:58.299 0.8s”, “2016-09-15 20:59:58.688 1.041s”, “2016-09-15 20:59:59.591 1.412s”, “2016-09-15 21:00:00.464 1.466s”, “2016-09-15 21:00:00.741 1.581s”, “2016-09-15 21:00:00.748 2.31s”, “2016-09-15 21:00:00.966 0.381s”, “2016-09-15 21:00:02.066 2.62s” ]

출력: 7

문제 해설

이번 테스트의 마지막 문제이고, 가장 어려운 문제입니다. 초당 최대 처리량이 되는 구간 윈도우를 찾아야 하는 문제인데요. 당연히 처음부터 끝까지 스캔하기에는 범위가 너무 크고, 게다가 ms 단위로 되어 있기 때문에 첫 로그 시각부터 마지막 로그 시각까지 1ms씩 증가시키면서 1000ms 단위의 슬라이딩 윈도우로 풀면 24 * 3600 * 1000 * n * 1000ms 만큼의 연산이 필요하기 때문에 이렇게는 풀 수가 없습니다.

그렇다고 각 로그의 시작 시각부터 마지막 시각까지 1ms 씩 움직이면 time(ms) * n^2 이 되며, time(ms)의 값은 대부분 천 단위 이상이기 때문에 마찬가지로 타임아웃이 발생하여 풀 수가 없습니다. 그런데 자세히 살펴보면 요청량이 변하는 순간은 각 로그의 시작과 끝뿐임을 알 수 있습니다. 따라서, 각 로그 별 2번의 비교 연산만 수행하면 되며 2 * n^2, 빅오로 정리하면 O(n^2)에 풀 수가 있습니다. 빅오에서 제거된 상수항도 매우 작기 때문에 이 경우 무리 없이 문제를 풀 수 있게 되며 C++ 기준으로 10ms를 넘지 않습니다.

물론, 이 문제는 윈도우를 사용하지 않고도 풀 수 있는 방법이 있습니다. 효율적인 알고리즘을 쓴다면, O(n log n)으로 풀 수 있는 방법도 있으니 한 번 고민해보세요. 이 문제는 가장 어려운 문제였던 만큼 정답률은 가장 낮은 17.99%입니다.

JAVA 예제

---

엄청나게 어려웠다. 코딩이 어려운게 아니라 문제를 이해하기가 너무 어려웠다. 결국 며칠을 걸려서 이해해서 코드를 작성하였다. 이게 더이상 코딩 테스트라기 보다는 문제이해력과, 해결능력을 보는게 더 큰 목적인 것도 같다.

건수를 구하는 핵심로직 부분은 인터넷을 참조하여 작성하였는데, 아직도 조금 이해가 안가는 부분이 있고 조금더 생각해봐야 할 것 같다. 

startDtm <= targetVo.getEndedDtm() && startDtm + 999 >= targetVo.getStartDtm()

기본적으로 처리는 다음 과정을 거친다.

1. 문제 입력을 파싱하여 시작시각과 종료시각을 구한다.
2. 시작시각과 종료시각을 long으로 계산을 간단하게 처리.
3. o(n^2)으로 list를 이중for문으로 모두 검사하여 각 구간별 수행갯수를 체크한다.

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
 
public class Traffic {
    
    public static class LogVo {
        
        long startDtm, endedDtm;
        String orgStr;
        
        public LogVo(long startDtm, long endedDtm, String orgStr) {
            this.startDtm = startDtm;
            this.endedDtm = endedDtm;
            this.orgStr = orgStr;
        }
        
        public long getStartDtm() {
            return startDtm;
        }
        
        public long getEndedDtm() {
            return endedDtm;
        }
    }
    
    public static void main(String[] args) {
        System.out.println(solution(new String[]{"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"}));
        System.out.println(solution(new String[]{"2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"}));
        System.out.println(solution(new String[]{"2016-09-15 20:59:57.421 0.351s"
                , "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s"
                , "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s"
                , "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s"
                , "2016-09-15 21:00:00.748 2.31s", "2016-09-15 21:00:00.966 0.381s"
                , "2016-09-15 21:00:02.066 2.62s"}));
    }
    
    private static int solution(String[] input) {
        ArrayList<LogVo> list = new ArrayList<LogVo>(); // LogVo를 담을 List
        
        SimpleDateFormat dt = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        for(String s : input) {
            String arr[]= s.split(" ");
            try {
                // 시간계산을 간단히 처리하기 위해서 모두 시작시각, 종료시각을 long으로 처리
                long endedDtm = dt.parse(arr[0]+" "+arr[1]).getTime();
                long proceDtm = (long)(Double.parseDouble(arr[2].replace("s", ""))*1000); 
                long startDtm = endedDtm - proceDtm + 1;
                // LogVo를 생성하여 list에 추가
                list.add(new LogVo(startDtm, endedDtm, s));
            } catch (ParseException e) {
                e.printStackTrace();
                return -1;
            }
        }
        
        int maxCnt = 0; // 최대값
        for(LogVo sourceVo : list) {
            long startDtm = sourceVo.getStartDtm(); // 시작시각
            long endedDtm = sourceVo.getEndedDtm(); // 종료시각
            int startCnt = 0; // 현재 로그 시작구간에서 실행중이 트랜젝션 갯수
            int endedCnt = 0; // 현재 로그 종료구간에서 실행중이 트랜젝션 갯수
            for(LogVo targetVo : list) {
                if(startDtm <= targetVo.getEndedDtm() && startDtm + 999 >= targetVo.getStartDtm()) {
                    startCnt++;
                }
                if(endedDtm <= targetVo.getEndedDtm() && endedDtm + 999 >= targetVo.getStartDtm()) {
                    endedCnt++;
                }
            }
            maxCnt = startCnt > maxCnt ? startCnt : maxCnt;
            maxCnt = endedCnt > maxCnt ? endedCnt : maxCnt;
        }
        return maxCnt;
    }
}

1차시 마지막 문제까지 모두 JAVA 버젼으로 정리하여서 뿌듯하긴 하지만, 깔끔하지 못한 알고리즘에 내심 마음이 안좋다.