[프로그래머스] 표 병합 JS

문제 링크

첫 풀이(틀림)

function solution(commands) {
    var answer = [];
    let parent = Array.from({ length: 51}, (e, i) => Array.from({ length: 51 }, (e2, i2) => [i, i2]))
    //50*50 배열
    let arr = Array.from({ length: 51 }, e => Array(51).fill(null))

    const findParent = (x, y) => {
        if (parent[x][y][0] == x && parent[x][y][1] == y) return [x, y]
        return parent[x][y] = findParent(parent[x][y][0], parent[x][y][1])
    }
    const union = (x1, y1, x2, y2) => {
        if (x1 === x2 && y1 === y2) return
        let parentA = findParent(x1, y1)
        let parentB = findParent(x2, y2)
        if (parentA[0]=== parentB[0]&&parentA[1]=== parentB[1]) return
        const value = arr[parentA[0]][parentA[1]] !== null ? arr[parentA[0]][parentA[1]] : arr[parentB[0]][parentB[1]];
        for (let i = 1; i < 51; i++) {
            for (let j = 1; j < 51; j++) {
                let temp = findParent(i, j)
                if (parentB[0] === temp[0] && parentB[1] === temp[1]) {
                    parent[i][j] = parentA
                    arr[i][j] = value
                }
            }
        }
    }
    commands.forEach(c => {
        let command = c.split(" ")
        //5가지 명령어 구분하기
        if (command[0] === "UPDATE" && command.length === 4) {
            //그룹 확인=>부모의 값만 갱신
            let p = findParent(Number(command[1]), Number(command[2]))
            arr[p[0]][p[1]] = command[3]
        } else if (command[0] === "UPDATE" && command.length === 3) {
            for (let i = 1; i < 51; i++) {
                for (let j = 1; j < 51; j++) {
                    if (arr[i][j] === Number(command[1])) arr[i][j] = Number(command[2])
                }
            }
        } else if (command[0] === "MERGE" && command.length === 5) {
            //그룹의 부모들도 갱신해야힘(unMerge때문에)
            union(Number(command[1]), Number(command[2]), Number(command[3]), Number(command[4]))
        } else if (command[0] === "UNMERGE" && command.length === 3) {
            //해당 위치의 부모값을 갖고 있는 노드들 구하기
            let p = findParent(Number(command[1]), Number(command[2]))
            let value = arr[p[0]][p[1]]
            for (let i = 1; i < 51; i++) {
                for (let j = 1; j < 51; j++) {
                    let temp = findParent(i, j)
                    if (p[0] === temp[0] && p[1] === temp[1]) {//부모가 같으니끊어내기
                        parent[i][j] = [i, j]
                        arr[i][j] = null
                    }
                }
            }
            arr[Number(command[1])][Number(command[2])] = value
        } else if (command[0] === "PRINT" && command.length === 3) {
            let p = findParent(Number(command[1]), Number(command[2]))
            arr[p[0]][p[1]] == null ? answer.push("EMPTY") : answer.push(arr[p[0]][p[1]])
        }
    })
    return answer;
}

실행 결과

시행착오

1. union할때 값이 없는 애가 처음 인자일 수 있다.
   역시 제일 중요한건 주어진 문제를 온전히 이해하기!!

2. unmerge는 for문으로 순서대로 하기 때문에 union에서 자식의 부모값도 최상위 부모로 바꿔주지 않으면 타고 들어갈 수 없다.

3. B가 C의 부모인 상태에서 A와 C를 병합하려고 하면 B와 C의 부모를 모두 업데이트해야한다. C의 부모만 A로 수정하면 문제 발생.

4. 셀을 class화 해서 solution의 함수들을 빼줘야한다.
   클래스와 재활용 할 수 있는 코드 함수화를 습관화 하자!

정답 풀이

class Node는 배열의 값이므로 몇번째 인덱스인지 식별하지 않아도 된다.
값과 부모/자식 배열만 있으면 된다.
merge는 앞에 있는 값이 n2 이다.

const Cell = class {
    constructor() {
        this.parent = null
        this.child = []
        this.value = null;
    }
    findParent() {
        if (this.parent) return this.parent
        return this
    }
    getValue() {
        return this.findParent().value
    }

    updateValue(newValue) {
        this.findParent().value = newValue
    }
    merge(n2) {
        let parent2 = n2.findParent()
        let myParent = this.findParent()
        if (parent2 === myParent) return
        myParent.child.forEach(c => {
            c.parent = parent2
            parent2.child.push(c)
        })
        // parent2에 소속됐으니 자식 초기화
        myParent.child = []
        myParent.parent = parent2
        parent2.child.push(myParent)
        if (parent2.value === null) parent2.value = myParent.value
        myParent.value = null
    }
    unmerge() {
        let p = this.findParent()
        let v = this.getValue()
        p.child.forEach(c => {
            c.parent = null
            c.value = null
        })
        p.value = null
        p.child = []
        p.parent = null
        this.value = v
    }
}
function solution(commands) {
    let answer = []
    let arr = Array.from({ length: 51 }, e => Array.from({ length: 51 }, e => new Cell()))
    commands.forEach(c => {
        let command = c.split(" ")
        //5가지 명령어 구분하기
        if (command[0] === "UPDATE" && command.length === 4) {
            arr[Number(command[1])][Number(command[2])].updateValue(command[3])
        } else if (command[0] === "UPDATE" && command.length === 3) {
            for (let i = 1; i < 51; i++) {
                for (let j = 1; j < 51; j++) {
                    if (arr[i][j].value === command[1]) arr[i][j].updateValue(command[2])
                }
            }
        } else if (command[0] === "MERGE") {
            if (Number(command[1]) !== Number(command[3]) || Number(command[2]) !== Number(command[4])) {
                const n2 = arr[Number(command[1])][Number(command[2])]
                arr[Number(command[3])][Number(command[4])].merge(n2)
            }
        } else if (command[0] === "UNMERGE") {
            arr[Number(command[1])][Number(command[2])].unmerge()
        } else if (command[0] === "PRINT") {
            arr[Number(command[1])][Number(command[2])].getValue() == null ? answer.push("EMPTY") : answer.push(arr[Number(command[1])][Number(command[2])].getValue())
        }
    })
    return answer
}