[JS] 외벽 점검

까다로운 문제였고 접근할 수 있는 방법이 굉장히 많고 생각할 거리도 많은 문제였다.

 

1 STEP) 원형 구조를 어떻게 구현할지

코테에서 원형구조를 구현하려면 보통 2가지 방법을 많이 쓴다.

1. 원형 링크드 리스트 구현

2. 리스트 2개를 이어붙임

 

사실 2번이 코테볼때는 조금 더 좋은 조건인거 같긴 하다. 특히 이번문제같은 경우 리스트 2개를 이어붙인 구조의 원형리스트를 구현한다면 조금더 쉽게 해결할 수 있을 거 같다.

 

예를들어서 1번예제를 리스트로 표한한다면

 

[1, 5, 6, 10] 이므로

 

[0,1,0,0,0,1,1,0,0,0,1,0] 가된다. 이 를 2번 이어붙인다면 [0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0] 가 된다.

 

1번의 정답인 4m를 10번에, 2m를 5번에 둔다고 생각해보자. 해당 구간의 값들을 0으로 바꿔준다면

[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0] 왼쪽같은 배열이 나오고 0이쭉 나오는 구간이 길이가 12 이상이므로 정답처리를 해결할 수 있다.

 

그런데 이번에는 원형리스트를 구현해본지도 좀 된거 같아서 그냥 원형리스트를 구현해서 사용해보았다.

 

2 STEP) 완전탐색

문제조건

 

문제 조건에서 유추할 수 있듯이 해당 문제는 순열,조합 을 활용한 완전탐색을 적용해볼만 문제이다. 단, weak에는 완전탐색을 하기에 무리가 있어 보인다. 

 

따라서 dist의 조합을 뽑아서 해결할 수 있을꺼라 생각했다.

 

 

1. dist의 길이를 1~n까지 천천히 순회 

   이때 dist를 역정렬해서 앞에서부터 사람들을 구하면 된다. 어차피 사람들의 수를 구하는 문제이기 때문에 순열로 n명을 뽑아낼 필요가 없다.

 

2. dist의 길이에 해당되는 순열들을 구함

  -> ex) [1,5]에서 2명을 뽑는다면 [1,5] , [5,1]

3. week지점에서 어느지점부터 공사를 해야될지 모르므로 한 지점씩 시작지점이라고 생각한 후 공사의 유무를 확인한다.

 

4. 공사의 유무??!

  공사의 유무는 week의 한지점부터 dist만큼 간 후, 원형 리스트를 참고하며 week부분을 찾아서 거기서부터 다시 dist만큼 보수하는 방식으로 구현하였다.

 

 

 

 

++ 사실 조금은 투박하게 푼 감이 있다. 조합 , 원형리스트, 그리디 여러가지 알고리즘을 짬뽕시켜서 경우의수를 체크하다보니 그만큼 효율적인 코드는 나오지 못한거 같다.

 

실제로 22번 테스트코드는 엄밀히(?) 말하면 통과하지 못했다. 아마 8개짜리 dist가 들어오고 list도 200인거 같아서 dist의 크기를 7까지만 순회하도록 해서 어거지로(?) 사실 해결한 문제이다. (굳이 원형리스트로 구현해서 그럴수도)

 

 

 

 

class Node {
    constructor (isWeek,idx){
        this.isWeek = isWeek
        this.idx = idx
        this.next = null
        this.prev = null
    }
}

class CirculrLinkedList {
    constructor (node){
        this.head = node
        this.size = node ? 1 : 0
    }
    
    push(node){
        if(this.size<1) this.head = node
        else if(this.size===1) {
            this.head.next = node
            this.head.prev = node
        } else {
            this.head.prev.next = node
            this.head.prev = node
            node.next = this.head
        }
        this.size ++
    }
    
      
    print(){
        let node = this.head
        for (let i = 0 ; i < this.size ; i++){
            process.stdout.write(`${node.isWeek?1:0}-`)
            node = node.next
        }
        
            console.log()
    }
    
  
    isClean(){
        let node = this.head
        for (let i = 0 ; i < this.size ; i++){
            if(node.isWeek === true) return false
            node = node.next
        }
        return true
    }
    
    cleanCircle(order,start) {
        let node = this.head
        for (let i = 0 ; i < start ; i++) node = node.next
        for (const dist of order){
            let cnt = 0
            while(!node.isWeek && cnt <= this.size) {
                node = node.next
                cnt++
            }
            
            for (let i = 0 ; i <= dist ; i++){
                node.isWeek = false
                node = node.next
            }
        }
    }
}

const getPermutation = (ary,n) => {
    if(n===1) return ary.map(v => [v])
    const ret = []
    ary.forEach((fixed,idx) => {
        const rest = [...ary.slice(0,idx), ...ary.slice(idx+1)];
        const combinations = getPermutation(rest,n-1)
        const attach = combinations.map(v => [fixed,...v])
        ret.push(...attach)
    })
    return ret
}

function solution(n, weak, dist) {
    
    const makeCircle = () => {
        const ret = new CirculrLinkedList()
        for (let i = 0 ; i < n ; i++){
            ret.push(new Node(weak.includes(i)?true:false,i))
        }
        return ret
    }
    
    
    for (let i = 0 ; i < (dist.length<8?dist.length+1:dist.length) ; i++){
        const orders = getPermutation(dist,i)
        for (const order of orders) {
            for (const start of weak){
                const cirList = makeCircle()
                cirList.cleanCircle(order,start)
                if(cirList.isClean()) return order.length
            }
            
        }
    }
    
    return -1
}