[개발일지] - 433(주말근무)

11시 전쯤에 출근해서 테스트를 진행했는데

중간 중간 테스트가 밀리고 계속 수정하고 

다른쪽에서 에러가 발생하는 등 문제가 있어서 결국 12시가 넘어버렸다.

 

아마 오늘 퇴근은 못할 것 같은데 대부분 실제 코드 관련이라 회고를 마땅히 적을 내용도 없는 것 같다.

 

 

(1).백준 2056번 작업은 각각의 선행 작업이 존재하고 작업들의 처리 시간이 존재할 때

모든 작업을 마치기 위한 최소시간을 구해야 하는 문제였다.

 

일단 위상정렬 태그로 문제를 조회했으니 당연히 위상정렬을 기준으로 문제를 풀어야 했는데

여기서는 시간 조건까지 추가되어 있고 단순 정렬이 아니라 완료시점 최적화로 답이 하나로 고정되기 때문에

depth와 queue만 가지고 푸는 일반 위상정렬처럼 접근이 어려웠다.

 

일단 각각의 개체에서 depth를 지정해줬고(d) 각각에 할당된 리스트를 list에 할당하고

각각의 작업 시간 t는 순회하며 입력해줬다.

 

처리 방식은 의외로 간단했는데

전체 작업 잔여 개수를 depth처럼 left라는 개체에 담아두고

작업이 모두 끝나는 것을 감지하게 해서 while문을 순회시켰다.

 

내부에서는 현재 depth가 0인 경우에만 남은 작업 시간들을 jobTime에 담아줬고

구조분해할당, Math.min을 통해 남은 최저시간의 작업을 구해준 다음

depth가 0인 모든 작업에 최저작업시간을 제외해줬다.

 

이후 depth가 0이면서 남은 시간이 0인 작업을 찾은 다음

해당 작업은 완료된 것이기 때문에 left를 감소시켰고

해당 작업과 연계된 작업들의 depth를 1씩 감소시키는 순회문을 작성해줬으며

이 작업은 더이상 연산되지 않도록 depth를 -1로 변경시켜서 감지되지 않도록 했다.

 

처음에는 key in graph 순회문 내부에 시간 감소 및 depth감소를 모두 넣었었는데

앞부분 depth에서 처리된 경우 뒤에 있는 작업이 완료되지 않았는데

이번 작업에서 depth가 0인 것 처럼 감지되는 경우가 있어서 시간이 반토막나서 출력되었기 때문에

시간 처리를 먼저 진행한 다음 다시 depth 처리하는 작업을 진행하도록 분리 후 통과될 수 있었다.

const input = `7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6`.split('\\n').map(el => el.split(' ').map(Number))

const graph = {}
let left = input[0][0]
let time = 0
for(let i = 1 ;  i < input.length ; i++){
    graph[i] = {d : 0 , list : new Array()}
}

for(let i = 1 ; i < input.length ; i++){
    graph[i].t = input[i][0]
    graph[i].d = input[i][1]
    for(let j = 2 ; j < input[i].length ; j++){
        graph[input[i][j]].list.push(i)
    }
}

while(left > 0){
    const jobTime = []
    for(let key in graph){
        if(graph[key].d == 0){
            jobTime.push(graph[key].t)
        }
    }
    
    const timePass = Math.min(...jobTime)
    time += timePass
    
    for(let key in graph){
        if(graph[key].d == 0){
            graph[key].t -= timePass
        }
    }
    
    for(let key in graph){
        if(graph[key].d == 0 && graph[key].t == 0){
            graph[key].d = -1
            left--
            for(i = 0 ; i < graph[key].list.length ; i++){
                graph[graph[key].list[i]].d -= 1
            }
        }
    }
}

console.log(time)

 

 

(2).백준 1766번 문제집은 각 난이도별의 문제가 있지만

특정 문제를 먼저 풀어야만 풀 수 있는 문제들이 존재한다고 할 때

문제를 풀어야 하는 순서를 출력해야 하는 문제였다.

 

기본 틀은 위상정렬이었지만 범위가 상당히 컸고

출력해야 하는 값은 풀 수 있는 최저난이도(작은 숫자) 순서대로 진행해야 했기 때문에

sort를 잠깐 생각했지만 시간복잡도가 박살날 것 같아서 최소힙을 사용해서 문제를 해결하기로 했다.

 

일단 기존 위상정렬 느낌대로 depth와 next 값들을 넣어준 다음 힙 입력 및 출력 메서드를 생성해줬는데

입력의 경우 간단히 마지막에 넣고 부모 노드의 값이 더 큰 경우에만 교체하는 방식으로 루트까지 비교했고

출력의 경우에는 루트값을 뺀 다음

루트의 위치에 마지막 값을 가져와 넣어주고 다시 자식 노드들과 비교해 제일 작은 값을 부모위치에 할당했다.

 

중간에 무한출력이 터져버려서 당황했는데

queue 체크를 뒤에서 length == 0으로 했는데

queue[0] = queue.pop() 부분에서 계속 할당해버리기 때문에

길이가 1보다 작아지는 시점이 나오지 않아서 무한루프에 갇혀있었던 것이었다.

 

테스트를 할 때는 완전히 비우지는 않고 10여개 대충 넣어보고 7~8개 잘 나오는 것만 확인했는데

어쨌거나 length가 1인 경우 비교고 뭐고 할 필요 없기 때문에 해당 값을 리턴하는 것으로 해결했다.

const input = `4 2
4 2
3 1`.split('\\n').map(el => el.split(' ').map(Number))

const depth = new Array(input[0][0] + 1).fill(0)
const next = new Array(input[0][0] + 1)
const queue = []
const result = []

for(let i = 1 ; i <= input[0][0] ; i++){
    next[i] = new Array()
}

for(let i = 1 ; i < input.length ; i++){
    const [before, after] = input[i]
    depth[after]++
    next[before].push(after)
}

for(let i = 1 ; i < depth.length ; i++){
    if(depth[i] == 0){
        queue.push(i)
    }
}

const pushQueue = (num) => {
    let indexNow = queue.length
    queue.push(num)
    while(indexNow > 0){
        parentIndex = Math.floor((indexNow - 1) / 2)
        if(queue[parentIndex] < queue[indexNow]){
            break
        }
        else{
            const temp = queue[parentIndex]
            queue[parentIndex] = queue[indexNow]
            queue[indexNow] = temp
            indexNow = parentIndex
        }
    }
}

const popQueue = () => {
    const result = queue[0]
    let indexNow = 0
    
    if(queue.length == 1){
        queue.pop()
        return result
    }
    
    queue[0] = queue.pop()

    while(queue[indexNow] > queue[indexNow * 2 + 1] 
          || queue[indexNow] > queue[indexNow * 2 + 2]){
        if(queue[indexNow * 2 + 1] > queue[indexNow * 2 + 2]){
            const temp = queue[indexNow]
            queue[indexNow] = queue[indexNow * 2 + 2]
            queue[indexNow * 2 + 2] = temp
            indexNow = indexNow * 2 + 2
        }
        else{
            const temp = queue[indexNow]
            queue[indexNow] = queue[indexNow * 2 + 1]
            queue[indexNow * 2 + 1] = temp
            indexNow = indexNow * 2 + 1
        }
    }

    return result
}

while(queue.length > 0){
    const now = popQueue()
    result.push(now)
    for(let i = 0 ; i < next[now].length ; i++){
        checkIndex = next[now][i]
        depth[checkIndex]--
        if(depth[checkIndex] == 0){
            pushQueue(checkIndex)
        }
    }
}

console.log(result.join(' '))