표 병합

https://school.programmers.co.kr/learn/courses/30/lessons/150366

프로그래머스

구현 문제이다.

표 ( table ) 의 기능들 ( update, replace, merge, unmerge, print ) 을 구현하면 된다.

가장 성능에 민감한 기능은 replace 로  N^2 가 소요된다. 이 부분은 mapping table 을 두어 개선할 수 있지만
문제가 시간 복잡도에 민감하지 않으므로 구현을 가져갈 수 있다.

그 다음으로 merge 기능의 예외 처리가 필요한데 동일 셀의 접근을 주의하여 구현한다.

 

merge 는 DS 를 따로 두어 linked ( 병합된 셀들의 집합 ) 으로 관리한다.

function getNormalData(value = undefined) {
    return {
        value,
    };
}

function getMergeData(value = undefined) {
    return {
        value,
        linked: [],
    };
}

function linkedIndex(r, c) {
    return (r - 1) * 50 + (c - 1);
}

function IndexLinked(i) {
    return [Math.floor(i / 50), i % 50];
}

function merge(table, r, c, r2, c2) {
    if (r == r2 && c == c2) return;
    
    if (table[r - 1][c - 1].linked 
        && table[r - 1][c - 1].linked.includes(linkedIndex(r2, c2))) {
        return;
    }
    else if (table[r2 - 1][c2 - 1].linked 
        && table[r2 - 1][c2 - 1].linked.includes(linkedIndex(r, c))) {
        return;
    }

    var a = table[r - 1][c - 1].value;
    var b = table[r2 - 1][c2 - 1].value;

    var value = undefined;
    if (a !== undefined && b !== undefined) {
        value = a;
    } else {
        value = a === undefined ? b : a;
    }

    var mergeData;
    if (table[r - 1][c - 1].linked) {
        mergeData = table[r - 1][c - 1];
        mergeData.value = value;

        if (table[r2 - 1][c2 - 1].linked) {
            var linked = table[r2 - 1][c2 - 1].linked;

            linked.forEach(link => {
                var [x, y] = IndexLinked(link);
                table[x][y] = mergeData;
            })

            mergeData.linked = mergeData.linked.concat(linked);
        } else {
            mergeData.linked.push(linkedIndex(r2, c2));

            table[r2 - 1][c2 - 1] = mergeData;
        }
    } else if (table[r2 - 1][c2 - 1].linked) {
        mergeData = table[r2 - 1][c2 - 1];

        mergeData.value = value;
        mergeData.linked.push(linkedIndex(r, c));

        table[r - 1][c - 1] = mergeData;
    } else {
        mergeData = getMergeData(value);

        mergeData.linked.push(linkedIndex(r, c), linkedIndex(r2, c2));

        table[r - 1][c - 1] = mergeData;
        table[r2 - 1][c2 - 1] = mergeData;
    }
}

function unmerge(table, r, c) {
    if (table[r - 1][c - 1].linked) {
        var linked = table[r - 1][c - 1].linked;
        var value = table[r - 1][c - 1].value;

        linked.forEach(link => {
            var [x, y] = IndexLinked(link);
            table[x][y] = getNormalData();
        })

        table[r - 1][c - 1] = getNormalData(value);
    }
}

function update(table, r, c, value) {
    table[r - 1][c - 1].value = value;
}

function replace(table, prev, aftr) {
    for (var i = 0; i < 50; i++) {
        for (var j = 0; j < 50; j++) {
            if (table[i][j].value == prev) {
                table[i][j].value = aftr;
            }
        }
    }
}

function print(table, r, c) {
    var value = table[r - 1][c - 1].value;
    return value === undefined ? "EMPTY" : value;
}

function solution(commands) {
    var answer = [];

    var table = new Array(50);
    for (var i = 0; i < 50; i++) {
        table[i] = new Array(50);
        for (var j = 0; j < 50; j++) {
            table[i][j] = getNormalData();
        }
    }

    commands.forEach(command => {
        var args = command.split(' ');
        switch (args[0]) {
            case 'UPDATE':
                if (args.length == 4) {
                    update(table, parseInt(args[1]), parseInt(args[2]), args[3]);
                } else {
                    replace(table, args[1], args[2]);
                }
                break;
            case 'PRINT':
                answer.push(print(table, parseInt(args[1]), parseInt(args[2])));
                break;
            case 'MERGE':
                merge(table, parseInt(args[1]), parseInt(args[2]), parseInt(args[3]), parseInt(args[4]))
                break;
            case 'UNMERGE':
                unmerge(table, parseInt(args[1]), parseInt(args[2]));
                break;
        }
    });

    return answer;
}