[JS] [1차] 추석 트래픽

누적합과 Map 자료형을 활용해서 해결하였다.

 

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

프로그래머스

 

 

문제는 단순하지만 ms까지 시간이 주어지는 바람에 조금 까다로웠고 생각할 거리가 조금 있는 문제였다.

 

 

해당 문제를 해결하기 위해서 누적합 개념을 적용해볼 수 있다. 시간은 0부터 1씩 증가하는 형태의 데이터로 생각할 수 있다.

0ms부터 10ms까지의 상태를 배열로 나타낸다면

 

0,0,0,0,0,0,0,0,0,0,0 과 같은 형태로 나타낼 수 있다.

 

여기서 2ms부터 4ms까지 작업을 수행한다면 이 상태는

 

0,0,1,1,1,0,0,0,0,0,0 으로 나타낼 수 있다.

 

만약 3ms부터 5ms까지 작업을 수행한다면 이는

 

0,0,1,2,2,1,0,0,0,0,0 처럼 배열에 합하는 형식으로 나타낼 수 있다.

 

 

이처럼 작업이 한두개라면 단순하게 for문을 활용해서 더해줄 수 있다. 하지만 line이 2천개고 시간이 ms까지 들어오기에 배열의 크기는 24*60*60*100 대충 8600만 정도가 되게 된다.. 따라서 이런 방법은 사용할 수 없다.

 

누적합을 활용한 방법으로 방금해본 예제를 그대로 해보자.

 

2ms -> 4ms이므로 2번째와 4번째에 각각 +1,-1을 해준다.

 

0,0,1,0,-1,0,0,0,0,0,0

 

3ms -> 5ms이므로 3번째와 5번째에 각각 +1 , -1을 해준다.

0,0,1,1,-1,-1,0,0,0,0,0

 

자이제 배열을 0번째 인덱스부터 누적합을 구해가며 for문을 한바퀴 돌아준다.

0,0,1,2,1,0,0,0,0,0,0

 

즉, 결과가 똑같이 나오지만 for문은 한번만 순회하면 되게 된다.

 

 

 

이런 누적합의 성질을 활용해서 처음에 문제를 풀려고 했다.

 

 

하지만 8600개의 배열을 만들고 순회하는건 결코 적은 부담이 아니라 시간이 많이들어갔다. 아마 메모리에 공간을 할당하는데 시간이 많이 드는것 같다.

 

어차피 line의 수는 2000개정도이고 가장많은 개수만 구하면 되므로 배열을 만들지 않고 Map자료형을 통해서 누적합에 넣을 정보만 저장해주었다.

 

이후 for문을 돌며 map자료형에 적힌 누적합 정보들을 더해가며 최대 요청수를 찾았다.

 

 

주의할점은 2가지 정도가 있다.

 

1. 시작점이 음수로 나올 수 있는데 이경우 0으로 바꿔줘야 한다.

2. 요청이 종료되어도 1초까지는 개수로 쳐줘야한다. (예제 4번 케이스를 보면 된다.)

 

 

function solution(lines) {
    const map = new Map();
    
    //hh:mm:ss 형태를 ms로 변경
    const changeHHMMSSToMs = (time) => {
        const [h,m,s] = time.split(":")
        return (+h*60*60+ +m*60+ +s) * 1000
    }
    
    //ss.ms 형태를 ms로 변경
    const changeSMsToMs = (time) => {
        let [s,ms] = time.split("s")[0].split(".")
        s = s ? +s : 0
        ms = ms ? +ms : 0
        return s*1000 + ms
    }
    
    for(const line of lines){
        //시간을 몽땅 ms로 바꿈
        const [date,S,T] = line.split(" ")
        const [hms,ms] = S.split(".")
        
        let end = changeHHMMSSToMs(hms) + +ms
        let start = end - changeSMsToMs(T)
        //시작시간과 끝나는 시간을 고름
        
        start = start>0 ? start : 0 //start가 0보다 작다면 0으로 맞춰줌
        end = end += 999 //end가 되어도 1초동안은 처리한 요청으로 처리하기 위해 더해줌
        
        //map 자료형에 누적합 저장
        if(map.has(start)) map.set(start,map.get(start)+1)
        else map.set(start,1)
        
        if(map.has(end)) map.set(end,map.get(end)-1)
        else map.set(end,-1)
    }
    
    //누적합을 더해가며 i초에서 처리할 수 있는 작업의 개수를 구함
    let ret =0 
    let tmp = 0
    for (let i = 0 ; i < 24*60*60*1000 ; i++){
        if(map.has(i)) {
            tmp += map.get(i)
            if(ret<tmp) ret = tmp
        }
    }
    
    return ret
    
    
}