2017 카카오 공채 코딩테스트 - 추석 트래픽

풀이과정)

 

처음에는 0.001초씩 1초 범위의 스코프를 움직이며 로그검색을 해보았는데 이렇게 되면 지나치게 많은 연산이 필요하다. 

예를 들어 8시간의 로그를 검색하기 위해 8*60*60*1000*n(로그갯수) 번의 연산을 하게 되는데 이러면 시간초과로

문제를 풀 수가 없다. 이렇게 문제를 간단하고 무식하게 풀도록 냈을리가 없는 게 당연하지만 혹시 모르니 그냥 시도해보았다.

(당연히 실패)

 

이후 다른 풀이를 생각하던 도중 로그의 시작과 끝을 분석하면 되겠다는 포인트를 발견.

이유인 즉슨, 한 시점에서의 로그의 갯수가 변하는 경우는 새로운 로그가 시작되거나 기존의 로그가 끝나는 순간이기 때문이다.

 

우선 lines의 모든 로그들을 파싱하여 logArr이라는 배열에 담아두었다.

첫 번째 요소인 startSec는 처리시간의 시작점이다.

두 번째 요소인 finishSec는 처리시간의 종료점이다.

세 번째 요소인 duration은 처리시간이다.

 

그리고 해당 로그의 모든 처리시간의 시작점과 종료점들을 logPointArr라는 배열에 담아두었다.

(처음부터 끝까지 순차검색 용도이므로 리스트에 담아도 된다)

이후 오름차순으로 정렬하게 되면 가장 먼저 발생한 로그의 시작 or 종료 시점부터 순차적으로 저장이 된다.

 

앞서 말했듯이 순간 트래픽의 변경이 발생하는 부분은 새 로그의 추가나 기존 로그의 종료가 일어나는 시점이다.

따라서 logPointArr의 각 요소들(beginRange)과 1초 후 시점(endRange)을 범위로 지정하여 모든 로그들을 추적해나가면 각 구간의 트래픽 갯수를 알아낼 수 있다.

 

1. 로그의 시작점이 범위 안에 존재하거나

 

2. 로그의 종료점이 범위 안에 존재해야 한다.

 

3. 그리고 마지막으로 해당 로그에 범위가 포함되어 있는 경우가 있다

이 부분이 핵심인데 2번 까지는 진작 근접했으나 3번 케이스를 생각해내지 못해 하루 종일 문제와 씨름했다.

사실 생각해보면 굉장히 간단한 건데 자꾸 복잡하게 문제를 스스로 꼬았던 것 같다.

지금까지의 해당사항을 참고해 코드를 작성하면 정답이 나올 것이다.

 

 

 

 

 

 

언어 : Javascript

 

풀이)

 

function solution(lines) {
    var logArr = [];
    var logPointArr = [];
 
    lines.forEach(log => {
        var finishSec = (Number(log.substring(11, 13))*3600 + 
            Number(log.substring(14, 16))*60 + 
            Number( log.substring(17, 23)) )
        var duration = Number(log.substring(24, log.length-1))
        var startSec = Number((finishSec-duration+0.001).toFixed(3))
 
        logArr.push(
            [startSec, finishSec, duration]
        )
 
        logPointArr.push(
            finishSec
        )
        logPointArr.push(
            startSec
        )
    })
 
    var max = 0;
    logPointArr.sort()
    console.log(logPointArr)
 
    // 모든 로그의 처리 시작 및 끝 순간을 기준으로 분석한다
    logPointArr.forEach(log => {
        var beginRange = log
        var endRange = log + 1
        var count = 0; 
 
        logArr.forEach(logItem => {
            var startPoint = logItem[0]
            var finishPoint = logItem[1]
 
            if( (startPoint>=beginRange && startPoint<endRange) ||
                (finishPoint>=beginRange && finishPoint<endRange) ||
                (startPoint<=beginRange && finishPoint>=endRange) ) {
                    count++
                }
 
        })
 
        if(count>max) {
            max = count
        }
 
    })
 
    return max
}