[개발일지] - 482(주말)

(1)백준 1715번 카드 정렬하기는 카드를 정렬할 때 각 묶음의 카드 숫자를 비교해야 했고

한번에 두 묶음씩만 가능하다고 하기 때문에 오름차순으로 정렬해준 다음

간단하게 앞순서부터 더해주면 된다고 생각했고

가중치를 부여해서 빠르게 넣어주고 시간초과가 걸리면 그때 우선순위 큐를 구현할 생각이었는데 오답이 나왔다.

 

시간초과나 메모리 부족까진 이해했지만 왜 오답일까 예시를 바꿔서 넣어보니

1,2,2,4,4,4형태로 정렬되었다고 하더라도 1+2인 값이 앞에 들어가면 3,2,4,4,4처럼 순서가 바뀌고

사실 이 부분까지는 두 값이 최소값이라 상관없지만 5,4,4,4가 되어버리면 4+4가 아니라 5+4가 먼저 되기 때문에

결론적으로는 최소값끼리 합하는 방식이 되지 않아서 최소힙을 구현해야 했다.

const input = `10
2
4
4
7
8
9
1
5
4
2`.split('\\n').map(Number)

input.shift()

input.sort((a,b) => a-b)

let count = input.length - 1
let result = input[0] * count

for(let i = 1 ; i < input.length ; i++){
    result += input[i] * count
    count--
}

console.log(result)

 

결국 최소 힙을 사용해서 전체 값 입력 후 꺼내서 비교해야 했는데

두개의 비교가 필요하기 때문에 while문 내부에서는 길이가 1초과인 경우에만 반복하게 했고

내부에서 두개를 꺼낸 다음 합한 값을 result에 더하고 다시 배열 내부에 담아줬다.

 

최종적으로 결과는 나왔지만 하나만 입력되는 경우 while이 작동하지 않았기 때문에

수동으로 추가해줬는데 오히려 오답이 나와버렸다.

const input = `3
10
20
40`.split('\\n').map(Number)

const arr = []
let result = 0

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

const popFromHeap = () => {
    const popNumber = arr[0]
    const lastNum = arr.pop()
    if(arr.length === 0){
        return popNumber
    }
    arr[0] = lastNum
    
    let indexNow = 0
    while(arr[indexNow] > arr[indexNow*2+1] || arr[indexNow] > arr[indexNow*2+2]){
        const [child1, child2] = [indexNow*2+1, indexNow*2+2]
        if(arr[child1] > arr[child2]){
            const temp = arr[child2]
            arr[child2] = arr[indexNow]
            arr[indexNow] = temp
            indexNow = child2
        }
        else{
            const temp = arr[child1]
            arr[child1] = arr[indexNow]
            arr[indexNow] = temp
            indexNow = child1
        }
    }
    return popNumber
}

for(let i = 1 ; i < input.length ; i++){
    pushToHeap(input[i])
}

while (arr.length > 1) {
    const first = popFromHeap()
    const second = popFromHeap()
    const sum = first + second
    result += sum
    if(arr.length){
        pushToHeap(sum)
    }
}

//카드 비교 합이라 계산할 필요 없었던 부분
//if(arr.length){
//    result += arr[0]
//}

console.log(result)

 

문제를 보니 비교할 때 값을 구해야 하는 문제였기 때문에

결론적으로는 하나만 있어서 비교할 필요가 없기 때문에 하나일 경우 그냥 아무 연산을 안해도 되는 것이었고

while문은 두개 이상일 떄만 돌아가기 떄문에 오히려 추가로 작성한 코드를 지우니 정답으로 마무리할 수 있었다.