[Programmers] (Javascript) 추석 트래픽

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

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

 

▶ 코드 : 

function solution(lines) {
    let answer = 0;
    let data = [];
    let minTime = 100000000;
    let maxTime = 0;

    for (const line of lines)
    {
        var temp = line.split(' ');
        var time = temp[1].split(':');
        var h = parseInt(time[0]) * 3600;
        var m = parseInt(time[1]) * 60;
        var s = parseFloat(time[2]);

        var endTime = (h + m + s) * 1000;
        var startTime = endTime - (parseFloat(temp[2].split('s').join(''))*1000 - 1);
        data.push([startTime, endTime]);
    }
   
    // 문자열을 숫자로 바꾸어 저장
    // 초로 변환해서 해보자

    let count = 0;

    for (let i =0; i < data.length; i++)
    {
        let boundL = data[i][1];
        let boundR = boundL + 999;
        let temp = 1;

        for (let j = i+1; j<data.length; j++)
        {
            if (data[j][0] > boundR)
            {
                continue;
            }
            else
            {
                temp+=1;
            }
        }

        if (temp > count)
        {
            count = temp;
        }
    }
    return count;
}

 

▶ 문제 풀이 : 

1. 초기 각각의 로그 정보 문자열들에 대해 시간을 초의 누적으로 변환한다. 

  - 해당 문제의 경우 소수점 셋째자리까지 나타나 있기에 1000을 곱하여 정수형태로 변환한뒤 시작시간과 끝시간의 초(second)누적값을 data 배열에 저장했다.

2. 이제 해당 값들을 이용해 탐색하여 1초동안 처리된 로그수의 최대값을 찾아야하는데 초기 완전탐색을 이용해 구현했으나 시간초과가 나왔다.

3. 이로인해 로직에 변화를 주어야 했고, 종료시간을 기준으로 오름차순된 정렬된 데이터(lines)임에 착안하여 각 로그의 종료시간을 시작시간으로 하여 1초 내에 로그의 수를 탐색하면 된다고 생각했다.

4. 이후 각각의 구간별로 다른 로그들(현재 시작값이 되는 로그의 이후 처리된 로그들)과 비교하여 만일 현재 1초구간의 마지막시간(boundR)보다 해당 로그의 시작시간(data[j][0])이 큰 경우가 아니라면 count를 올려주었다.

 

로그 예시

- 위와 같이 로그가 종료시간을 기준으로 오름차순 정렬되어 있다면, 각 로그의 종료값 기준 1초내 다른 로그들과 겹치는 횟수를 세는 것이 가장 큰 count값을 얻을 수 있는 방법이다.

 

▶ 실패 코드 => 경우가 다르다.

이경우는 로그시간이 종료시간을 기준으로 오름차순이 아닐때 완전탐색으로 구현한 경우

let count = 0;
// 로그 중 어떤 로그시간의 endtime으로부터 1초내에 해당 시간이 포함되는지를 확인하면 탐색횟수를 줄일 수 있다.   
// 현재 방식은 로그시간이 종료시간을 기준으로 오름차순 정렬이 아닐때의 경우임
   
for (let i = minTime; i <= maxTime; i++ )
{
    let boundL = i;
    let boundR = i + 999;
    let temp = 0;

    for (const times of data)
    {
        if (times[1] < boundL || times[0] > boundR){
            continue;
        }
        else
        {
            temp += 1;
        }
    }

    if (temp > count)
    {
        count = temp;
    }
}