20200502 알고리즘

function solution(user_id, banned_id) {
    const answer = new Set()
    const ch = new Array(user_id.length).fill(0)
    const dis = new Array(banned_id.length).fill(0)
    
    function DFS(L){
        if (L === banned_id.length){
            answer.add(dis.concat().sort().join(''))
        }
        else {
            for (let i=0; i<user_id.length; i++){
                if (!ch[i]){
                    if (user_id[i].length === banned_id[L].length){
                        let alpha_cnt = 0
                        let star_cnt = 0
                        for (let j=0; j<user_id[i].length; j++){
                            if (banned_id[L][j] === '*'){
                                star_cnt += 1
                            } else if (banned_id[L][j] === user_id[i][j]){
                                alpha_cnt += 1
                            }
                        }
                        if (alpha_cnt + star_cnt === user_id[i].length){
                            ch[i] = 1
                            dis[L] = i
                            DFS(L+1)
                            ch[i] = 0
                        }    
                    }
                }
            }
        }
    }
    
    DFS(0)
    return answer.size
}

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

function solution(jobs) {
    const length = jobs.length
    jobs.sort((a,b) => a[0]-b[0])
    let waitQ = [] 
    const progressQ = [] 
    let total = 0
    let cur_time = 0
    while (jobs.length>0 || waitQ.length > 0){
        if (waitQ.length > 0){
            waitQ = waitQ.map(v => ({remain: v['remain'], time: v['time']+1}))
        } // waitQ time ++
        const requests = []
        while (true){
            if (jobs.length> 0 && jobs[0][0] === cur_time){
                requests.push(jobs.shift())
            } else break
        }
        if (requests.length > 0){
            requests.forEach(v => waitQ.push({remain: v[1], time: 0}))
        }
        if (progressQ.length > 0){
            let {remain, time} = progressQ[0]
            progressQ[0]['remain'] = remain - 1
            progressQ[0]['time'] = time + 1
            if (remain-1 === 0){
                total += progressQ[0]['time']
                progressQ.shift()
                //다음 작업 찾기
                if (waitQ.length > 0){
                    waitQ.sort((a,b) => b['remain'] -a['remain'])
                    progressQ.push(waitQ.pop())
                }
            }
        }// 진행 중 작업 있다.
        else if (!progressQ.length){
            if (waitQ.length > 0){
                waitQ.sort((a,b) => b['remain']-a['remain'])
                progressQ.push(waitQ.pop())    
            }
        }
        cur_time += 1
    }
    // 큐 채워져있는지 확인해야해
    if (progressQ.length > 0){
        total += progressQ[0]['time'] + progressQ[0]['remain']
    }
    return Math.floor(total / length)
}

function convert(minutes){
    let hour = Math.floor(minutes / 60)
    let minute = minutes % 60
    if (hour < 10) hour = `0${hour}`
    if (minute < 10) minute = `0${minute}`
    return `${hour}:${minute}`
}

function solution(n, t, m, timetable) {
    timetable = timetable.map(v => {
        const [hour, minute] = v.split(':')
        return Number(hour)*60+Number(minute)
    })
    timetable.sort((a,b) => a-b)
    let i=1;
    let cnt = 0 // 매 버스마다 몇명 태웠는지
    let s = 0 // array queue 를 가리키는 index
    while (i<=n){
        cnt = 0
        const cur = 540 + (t * (i-1))
        if (i == n){
            let tmp_s = s
            for (let j=tmp_s; j<timetable.length; j++){
                if (timetable[j] <= cur){
                   cnt += 1
                   tmp_s += 1
                   if (cnt === m) break
               }
            }
            if (cnt+1 <= m) return convert(cur)
            else return convert(timetable[s+(m-1)]-1)
        } else {
           for (let j=s; j<timetable.length; j++){
               if (timetable[j] <= cur){
                   cnt += 1
                   s += 1
                   if (cnt === m) break
               }
           }     
        }
        i += 1
    }
}

function solution(operations) {
    const q = []
    for(const v of operations){
        const [command, number] = v.split(' ')
        if (command === 'I'){
            q.push(Number(number))
        } else if (command === 'D'){
            if (q.length !== 0){
                if (number === '1' ){
                    q.sort((a,b) => a-b)
                    q.pop()
                } else {
                    q.sort((a,b) => b-a)
                    q.pop()
                }    
            }
        }
    }
    if (!q.length) return [0,0]
    else {
        const answer = [-2147000000, 2147000000]
        for (const v of q){
            if (v > answer[0]) answer[0] = v
            if (v < answer[1]) answer[1] =v
        }
        return answer
    }
}