5월 30일 알고리즘 연습

1. 요격 시스템

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

프로그래머스

 

function solution(targets) {
   targets.sort((a,b)=>a[1]-b[1]) //오름차순
    let prev = -1
    let answer = 0;
   for (target of targets) {
       const [start,end] = target
       if (prev <= start) {
           prev = end
           answer++
       }
   }
    return answer
}

라인을 생각하자

정렬을 해서 end가 낮은 라인부터 순회하면서 라인이 포함할 수 없을 때 다음 라인으로 갈아타는 방식으로 짠다

 

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

function solution(plans) {

    let stop = []
    let answer =[]
    const timeToNum = (str) => {
        return parseInt(str.split(":").join(""))
    }
    plans=plans.map(e=>[e[0],timeToNum(e[1]),timeToNum(e[2])]).sort((a,b)=>a[1]-b[1])
    let now = [plans[0]]
    for(let i = 1; i < plans.length; i++) {
        let [nowSubject,nowTime,nowPlaytime] = plans[i]
        let [subject,time,playtime]=now.pop()          
        let takeTime= (Math.floor(nowTime/100)-Math.floor(time/100))*60+nowTime%100-time%100
     
        if(playtime >takeTime) {
            //시간이 남아있는 경우
            stop.push([subject,time,playtime-takeTime])
        }
        else {
            //시간을 다 쓴 경
            answer.push(subject)
            let restTime = takeTime-playtime

                while(stop.length>0) {
                    const [stopSubject,stopTime,stopPlaytime] = stop.pop()
     
                    if (stopPlaytime > restTime) {
                        stop.push([stopSubject,stopTime,stopPlaytime-restTime])
                        break;
                    }
                    else {
                        restTime -= stopPlaytime
                        answer.push(stopSubject)
                    }
                }
            
        }
        now.push(plans[i])
    }
    answer.push(now[now.length-1][0])
    while (stop.length) {
        answer.push(stop.pop()[0])
    }
    return answer;
}

구현문제인데 까다로웠다 문제를 잘 읽고 분기처리를 잘하자