[JS] 스타 수열

스타수열을 만들기 위해서는 교집합이 될 숫자가 필요하다. 이 숫자를 star라고 생각해보자.

 

어떻게 보면 해당 문제는 이 star가 가장 많은 배열의 길이를 반환하는 문제라고 생각할 수 있다.

 

따라서 cnt배열을 하나 둔 후, 가장 많이 나온 숫자순으로 스타수열을 만들어서 만약 스타수열이라면 그 길이를 반환하면 된다. 이 과정을 일반 배열로 한다면 최대값을 찾을 때마다 n의 시간복잡도가 들어가므로 최대 힙을 활용하여 해결하였다.

 

1. cnt배열을 활용해서 a배열에서 나온 숫자들을 센다. 단, 연속해서 나온 부분은 빼준다.

2. cnt배열의 값들을 최대 힙에 하나씩 넣어준다.

3. 최대 힙을 하나씩 pop해나간다. 이때 star와 cnt에 담겨있는 숫자가 실제 스타수열을 만들었을때의 길이와 같다면 프로그램을 종료하고 그렇지 않다면 실제 스타수열의 길이를 cnt로 갱신하여 힙에 다시 넣어준다.

 

 

 

 

 

 

 

 

 

class maxHeap {
    constructor() {
        this.ary = [0]
    }
    
    swap(aIdx,bIdx) {
        const c = this.ary[aIdx]
        this.ary[aIdx] = this.ary[bIdx]
        this.ary[bIdx] = c
    }
    
    push(value) {
        this.ary.push(value)
        let idx = this.ary.length-1
        let parentIdx = ~~(idx/2)
        while(parentIdx>0&&this.ary[idx][1] > this.ary[parentIdx][1]){
            this.swap(idx,parentIdx)
            idx = parentIdx
            parentIdx = ~~(idx/2)
        }
    }
    
    pop() {
        if (this.ary.length===1) return undefined
        if (this.ary.length===2) return this.ary.pop()
        const ret = this.ary[1]
        this.ary[1] = this.ary.pop()
        let idx = 1
        
        while(idx<this.ary.length){
            const leftIdx = idx * 2
            const rightIdx = idx * 2 +1
            let mainIdx = leftIdx
            if(leftIdx>=this.ary.length) break
            if(rightIdx<this.ary.length && this.ary[rightIdx][1] > this.ary[leftIdx][1]) mainIdx = rightIdx
            
            if(this.ary[mainIdx][1]<this.ary[idx][1]) break
            this.swap(idx,mainIdx)
            idx = mainIdx
        }
        return ret
        
    }
}

function solution(a) {
    
    const cnt = Array(a.length).fill(0)
    const heap = new maxHeap()
    
    const getStarSequenceLen = (star) => {
        let ret = 0
        let tmp = -1
        for (const num of a){
            if(tmp===-1) tmp = num
            else if(tmp===star && num!==star){
                ret ++
                tmp = -1
            } else if(tmp!==star && num===star){
                ret ++
                tmp = -1
            }
        }
        return ret
    }
    
    if(a.length>1) cnt[a[0]] += 1
    for (let i = 1 ; i < a.length-1 ; i++){
        if(a[i-1]!== a[i] || a[i+1]!==a[i]) cnt[a[i]]+=1
    }
    if(a.length>1) cnt[a[a.length-1]] +=1
    
    
    
    
    for (let i = 0 ; i < cnt.length ; i++){
        heap.push([i,cnt[i]])
    }
    
    while(heap.ary.length>1){
        const [star,cnt] = heap.pop()
        const realLen = getStarSequenceLen(star)
        if (realLen === cnt) return cnt * 2
        heap.push([star,realLen])
    }
    
 
}