표 병합 (자바스크립트)

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

프로그래머스

문제는 각 커맨드에 따라 동작이 달라진다. 

구현 문제라 생각하여 자바스크립트의 Map을 활용하여 문제를 풀었다.

우선 UPDATE 커맨드 일 경우 입력되는 value는 문자 또는 숫자로 이루어진 문자열이라고 제한되어 있다. 

따라서 gr을 50*50으로 선언한 뒤 , 각 좌표에 숫자인 mergeId를 기입하여 추후 특정 좌표가 병합 되어 있는 상태인지 아닌지는 그 좌표에 입력되어 있는 값의 타입이 number라면 이는 병합 되어 있는 것으로 판단할 수 있었다.

const n = 50;
const gr = Array.from({ length: n + 1 }, () =>
    Array.from({ length: n + 1 }, () => '')
);

const mergeRecord = new Map();

const isMergedCoordinate = (x, y) => {
    return typeof gr[x][y] === 'number';
};

const stringfyCoordinate = (a) => `${a[0]}-${a[1]}`;
const parseCoordinate = (a) => a.split('-').map(Number);

mergeRecord의 key로는 mergeId로 관리하면서 그 값에는 문자열이 기록 될 value와 병합되어 있는 좌표들을 string으로 저장 될 nodes를 담아둔다. 이 때 nodes는 Set으로 관리하여 중복을 처리했다.

아래는 merge 하는 과정이다. 

1. a와 b 좌표를 입력 받았을 때 두 좌표 모두 병합 되어 있는 상태라면 a 병합 상태에 b 병합들을 담아준다.

2. a 또는 b가 병합 되어 있다면, 병합 되어 있지 않은 좌표에 병합 아이디를 기록하고 병합 기록에 그 좌표를 추가해준다.

3. 둘 다 병합 되어 있지 않다면, 병합 아이디를 통해 병합 기록에 담아준다. 

 

mergeId는 클로저로 관리하여 새로운 병합이 기록 될 거라면 이 id를 사용하고 +1 을 해준 것으로 처리했다. 

여기서 주의할 점은 병합 될 때 기록될 값은 값이 있는 것을 우선하며, 둘 다 있을 경우 a의 값을 사용해야 한다는 것이다.

let mergeId = 1;

const setMerge = (a, b) => {
    if (a[0] === b[0] && a[1] === b[1]) return;
    const isAMerge = isMergedCoordinate(...a);
    const isBMerge = isMergedCoordinate(...b);

    if (isAMerge && isBMerge) {
        // 1️⃣ 둘 다 병합된 상태 → 병합 아이디 통합
        const aMergeId = gr[a[0]][a[1]];
        const bMergeId = gr[b[0]][b[1]];

        if (aMergeId === bMergeId) return; // 이미 같은 그룹이면 무시

        const aRecord = mergeRecord.get(aMergeId);
        const bRecord = mergeRecord.get(bMergeId);

        // value 결정: A의 value 우선
        const value = aRecord.value || bRecord.value || '';

        for (const node of bRecord.nodes) {
            aRecord.nodes.add(node);
            const [x, y] = parseCoordinate(node);
            gr[x][y] = aMergeId;
        }

        aRecord.value = value;
        mergeRecord.delete(bMergeId);
    } else if (isAMerge) {
        // 2️⃣ A 병합됨 → B를 A 그룹에 편입
        const aMergeId = gr[a[0]][a[1]];
        const record = mergeRecord.get(aMergeId);
        const bValue = gr[b[0]][b[1]] || ''; // 덮기 전 값 저장

        gr[b[0]][b[1]] = aMergeId;
        record.nodes.add(stringfyCoordinate(b));

        if (record.value === '') record.value = bValue;
    } else if (isBMerge) {
        // 3️⃣ B 병합됨 → A를 B 그룹에 편입
        const bMergeId = gr[b[0]][b[1]];
        const record = mergeRecord.get(bMergeId);
        const aValue = gr[a[0]][a[1]] || ''; // 덮기 전 값 저장

        gr[a[0]][a[1]] = bMergeId;
        record.nodes.add(stringfyCoordinate(a));

        record.value = aValue || record.value;
    } else {
        // 4️⃣ 둘 다 비병합 상태 → 새 그룹 생성
        const value = gr[a[0]][a[1]] || gr[b[0]][b[1]] || '';

        gr[a[0]][a[1]] = mergeId;
        gr[b[0]][b[1]] = mergeId;

        const nodes = new Set([
            stringfyCoordinate(a),
            stringfyCoordinate(b),
        ]);

        mergeRecord.set(mergeId, { nodes, value });
        mergeId++;
    }
};

이제 unMerge를 구현하는 과정은 아래와 같다.

문제에 기입되어 있는 내용대로 병합에 해당 되는 셀들은 모두 실행 초기 상태로 돌아간다. 즉, "" 으로 돌리면 된다. 또한 value가 있었다면 입력으로 들어온 좌표에 이 value를 넣으면 된다.

const unMerge = (x, y) => {
    if (!isMergedCoordinate(x, y)) return;

    const mergeId = gr[x][y];
    const record = mergeRecord.get(mergeId);

    const valueToKeep = record.value;

    for (const node of record.nodes) {
        const [nx, ny] = parseCoordinate(node);
        gr[nx][ny] = '';
    }

    gr[x][y] = valueToKeep;
    mergeRecord.delete(mergeId);
};

아래는 각 커맨드에 따른 동작들을 구현한 것이다.

for (const str of commands) {
    const [command, xx, yy, z, tt] = str.split(' ');

    switch (command) {
        case 'UPDATE': {
            if (z) {
                // UPDATE x y value
                const [x, y] = [xx, yy].map(Number);
                if (isMergedCoordinate(x, y)) {
                    const mId = gr[x][y];
                    const record = mergeRecord.get(mId);
                    record.value = z;
                } else {
                    gr[x][y] = z;
                }
            } else {
                // UPDATE oldValue newValue
                for (const [mId, record] of mergeRecord.entries()) {
                    if (record.value === xx) record.value = yy;
                }
                for (let i = 1; i <= n; i++) {
                    for (let j = 1; j <= n; j++) {
                        if (gr[i][j] === xx) {
                            gr[i][j] = yy;
                        }
                    }
                }
            }
            break;
        }

        case 'MERGE': {
            const [ax, ay, bx, by] = [xx, yy, z, tt].map(Number);
            setMerge([ax, ay], [bx, by]);
            break;
        }

        case 'UNMERGE': {
            const [x, y] = [xx, yy].map(Number);
            unMerge(x, y);
            break;
        }

        case 'PRINT': {
            const [x, y] = [xx, yy].map(Number);

            if (gr[x][y]) {
                if (isMergedCoordinate(x, y)) {
                    const rec = mergeRecord.get(gr[x][y]);
                    answer.push(rec.value || 'EMPTY');
                } else {
                    answer.push(gr[x][y]);
                }
            } else {
                answer.push('EMPTY');
            }
            break;
        }
    }
}

====

전체 코드

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

    const n = 50;
    const gr = Array.from({ length: n + 1 }, () =>
        Array.from({ length: n + 1 }, () => '')
    );

    let mergeId = 1;
    const mergeRecord = new Map();

    const isMergedCoordinate = (x, y) => {
        // 병합된 셀은 number 타입의 mergeId를 저장
        return typeof gr[x][y] === 'number';
    };

    const stringfyCoordinate = (a) => `${a[0]}-${a[1]}`;
    const parseCoordinate = (a) => a.split('-').map(Number);

    const setMerge = (a, b) => {
        if (a[0] === b[0] && a[1] === b[1]) return;
        const isAMerge = isMergedCoordinate(...a);
        const isBMerge = isMergedCoordinate(...b);

        if (isAMerge && isBMerge) {
            // 1️⃣ 둘 다 병합된 상태 → 병합 아이디 통합
            const aMergeId = gr[a[0]][a[1]];
            const bMergeId = gr[b[0]][b[1]];

            if (aMergeId === bMergeId) return; // 이미 같은 그룹이면 무시

            const aRecord = mergeRecord.get(aMergeId);
            const bRecord = mergeRecord.get(bMergeId);

            // value 결정: A의 value 우선
            const value = aRecord.value || bRecord.value || '';

            for (const node of bRecord.nodes) {
                aRecord.nodes.add(node);
                const [x, y] = parseCoordinate(node);
                gr[x][y] = aMergeId;
            }

            aRecord.value = value;
            mergeRecord.delete(bMergeId);
        } else if (isAMerge) {
            // 2️⃣ A 병합됨 → B를 A 그룹에 편입
            const aMergeId = gr[a[0]][a[1]];
            const record = mergeRecord.get(aMergeId);
            const bValue = gr[b[0]][b[1]] || ''; // 덮기 전 값 저장

            gr[b[0]][b[1]] = aMergeId;
            record.nodes.add(stringfyCoordinate(b));

            if (record.value === '') record.value = bValue;
        } else if (isBMerge) {
            // 3️⃣ B 병합됨 → A를 B 그룹에 편입
            const bMergeId = gr[b[0]][b[1]];
            const record = mergeRecord.get(bMergeId);
            const aValue = gr[a[0]][a[1]] || ''; // 덮기 전 값 저장

            gr[a[0]][a[1]] = bMergeId;
            record.nodes.add(stringfyCoordinate(a));

            record.value = aValue || record.value;
        } else {
            // 4️⃣ 둘 다 비병합 상태 → 새 그룹 생성
            const value = gr[a[0]][a[1]] || gr[b[0]][b[1]] || '';

            gr[a[0]][a[1]] = mergeId;
            gr[b[0]][b[1]] = mergeId;

            const nodes = new Set([
                stringfyCoordinate(a),
                stringfyCoordinate(b),
            ]);

            mergeRecord.set(mergeId, { nodes, value });
            mergeId++;
        }
    };

    const unMerge = (x, y) => {
        if (!isMergedCoordinate(x, y)) return;

        const mergeId = gr[x][y];
        const record = mergeRecord.get(mergeId);

        const valueToKeep = record.value;

        for (const node of record.nodes) {
            const [nx, ny] = parseCoordinate(node);
            gr[nx][ny] = '';
        }

        gr[x][y] = valueToKeep;
        mergeRecord.delete(mergeId);
    };

    for (const str of commands) {
        const [command, xx, yy, z, tt] = str.split(' ');

        switch (command) {
            case 'UPDATE': {
                if (z) {
                    // UPDATE x y value
                    const [x, y] = [xx, yy].map(Number);
                    if (isMergedCoordinate(x, y)) {
                        const mId = gr[x][y];
                        const record = mergeRecord.get(mId);
                        record.value = z;
                    } else {
                        gr[x][y] = z;
                    }
                } else {
                    // UPDATE oldValue newValue
                    for (const [mId, record] of mergeRecord.entries()) {
                        if (record.value === xx) record.value = yy;
                    }
                    for (let i = 1; i <= n; i++) {
                        for (let j = 1; j <= n; j++) {
                            if (gr[i][j] === xx) {
                                gr[i][j] = yy;
                            }
                        }
                    }
                }
                break;
            }

            case 'MERGE': {
                const [ax, ay, bx, by] = [xx, yy, z, tt].map(Number);
                setMerge([ax, ay], [bx, by]);
                break;
            }

            case 'UNMERGE': {
                const [x, y] = [xx, yy].map(Number);
                unMerge(x, y);
                break;
            }

            case 'PRINT': {
                const [x, y] = [xx, yy].map(Number);

                if (gr[x][y]) {
                    if (isMergedCoordinate(x, y)) {
                        const rec = mergeRecord.get(gr[x][y]);
                        answer.push(rec.value || 'EMPTY');
                    } else {
                        answer.push(gr[x][y]);
                    }
                } else {
                    answer.push('EMPTY');
                }
                break;
            }
        }
    }

    return answer;
}