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

(1).백준 14002번 가장 긴 증가하는 부분 수열 4는 기존 수열처리와는 다르게 해당하는 배열도 출력해야 하는 문제였다.

 

처음에는 어제 예상한 방식대로 마지막 숫자가 변경될 경우에만 체크하고

그 외에는 배열 끝에 push하는 방식으로 처리했었지만 오답이 나와버렸고

원인을 파악해보니 a,b,c,d에서 b가 대체되었고 그 뒤에 d가 대체되었다면 c까지 바뀌지 않았기 때문에

현재 arr에 담긴 내용은 a,b2,c,d2인 상태에서 대체되어버리지만 

실제로는 c가 바뀌지 않았기 때문에 a,b,c,d가 맞는 내용이라서 이 방식은 문제가 있었다.

 

결국 index를 통해 각각에 담기는 arr의 index를 기록하는 배열을 따로 생성해주고

beforeIndex를 통해서 이전에 바라보는 index를 조회해서 살짝 트리 느낌으로 해당 값 아래에 매달리게 진행했다.

 

이후로는 a, b, c, d, b2, d2 순서대로 들어온다고 하더라도

각각의 index는 [0,1,2,3,1,3]형태가 되어버리고

beforeIndex는[x,0,1,2,0,2]형태가 되기 때문에 마지막 대체된 d2를 기준으로 따라간다고 하더라도

d2가 바라보는 앞글자는 c가 되고 c가 바라보는 앞글자는 index1인 b가 되기 때문에

자연스럽게 a,b,c,d2 형태로 마무리가 될 수 있는 방식이 됐다.

 

이후 이 내용을 역순으로 한글자씩 추적해준 다음

shift로 넣어줄 경우 시간복잡도가 매 행동마다 O(N)이라 O(N^2)이 되기 때문에

모두 push로 넣은 값을 reverse로 정상 순서대로 바꿔준 다음 출력하는 방식으로 해결했다.

const input = `16
-60 -41 -100 8 -8 -52 -62 -61 -76 -52 -52 14 -11 -2 -54 46`.split('\n')[1].split(' ').map(Number)

const arr = []
const index = []
const beforeIndex = []
const result = []

for(let i = 0 ; i < input.length ; i++){
    let low = 0
    let high = arr.length

    while(low < high){
        let mid = Math.floor((low + high)/2)
        if(arr[mid] < input[i]){
            low = mid + 1
        } 
        else{
            high = mid
        }
    }

    if(low < arr.length){
        arr[low] = input[i]
    }
    else{
        arr.push(input[i])
    }
    index.push(low)
    if(low > 0){
        beforeIndex[i] = index.lastIndexOf(low-1)
    }
    
}

let now = index.lastIndexOf(arr.length-1)

while(now != undefined){
    result.push(input[now])
    now = beforeIndex[now]
}

console.log(arr.length)
console.log(result.reverse().join(' '))