younganswer
Problem SolvingSep 3, 2025

[프로그래머스] 150366 표 병합 (C/C++)

#Problem Solving#Coding Test#Algorithm#Programmers#150366#C/C++#Union Find
[프로그래머스] 150366 표 병합 (C/C++)

문제

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



풀이

문제를 처음 봤을 때는 일종의 DBMS를 구현하는 문제라고 생각했다. 그래서 처음에는 B-Tree 계열 자료구조를 활용하고, vector와 map을 hybrid container로 조합해 CRUD를 O(log N)으로 처리할 수 있도록 설계했다. 하지만 표의 크기가 50x50 이고 명령어의 개수가 1000개 이하인 것을 보고 시간 복잡도에 관련된 문제는 아니구나 생각하고 다시 단일 vector container로 구현했다.


MERGE 명령어를 지원해야한다는 점에서 바로 Union-Find 알고리즘이 떠올랐다. 다만 UNMERGE 명령어를 구현할 때 어려움이 있었는데, Union-Find 특성상 모든 노드가 항상 최상위 부모를 직접 가리키고 있지 않기 때문에 특정 그룹을 찾는게 어려웠다. 하지만 표 크기가 작은 덕분에 단순히 모든 셀을 순회하면서 같은 부모를 가지는 셀을 찾아 분리하는 방식으로 해결했다.


알고리즘 자체는 어렵지 않지만, 구현해야 할 기능이 많아서 시간이 많이 소요되는 문제였다.



메모

  • Segmentation fault, abort 등의 오류가 발생하면 UB 혹은 배열 크기를 확인하자.
  • 구조적 바인딩으로 선언된 변수는 람다에서 캡쳐할 수 없다.


소스 코드

C++17
#include <bits/stdc++.h>

#define SIZE 51

typedef std::vector<std::string> Record;
typedef std::vector<Record> Table;
typedef std::vector<std::string> Args;
typedef std::function<void(const Args &)> Handler;
typedef std::pair<size_t, size_t> Coordinate;

Table table(SIZE, Record(SIZE, ""));
std::vector<std::vector<Coordinate>> parent(SIZE, std::vector<Coordinate>(SIZE));

Args split(const std::string &source) {
    Args ret;
    std::string token;
    std::istringstream iss(source);

    while (iss >> token) {
        ret.push_back(token);
    }

    return ret;
}

Coordinate find(const Coordinate &current) {
    const auto [ r, c ] = current;

    if (parent[r][c] == current) {
        return current;
    }
    return parent[r][c] = find(parent[r][c]);
};

template <typename Func>
void forEach(Func &&f) {
    for (size_t i = 1; i <= 50; ++i) {
        for (size_t j = 1; j <= 50; ++j) {
            f(i, j);
        }
    }
}

std::vector<std::string> solution(std::vector<std::string> commands) {
    std::vector<std::string> answer;

    forEach([&] (size_t i, size_t j) {
        parent[i][j] = { i, j };
    });

    Handler update = [&] (const Args &args) {
        if (args.size() == 3) {
            const size_t r = std::stoul(args[0]);
            const size_t c = std::stoul(args[1]);
            const auto [ pr, pc ] = find({ r, c });

            table[pr][pc] = args[2];
        } else {
            forEach([&] (size_t i, size_t j) {
                if (table[i][j] == args[0] && Coordinate{ i, j } == find({ i, j })) {
                    table[i][j] = args[1];
                }
            });
        }
    };

    Handler merge = [&] (const Args &args) {
        const size_t r1 = std::stoul(args[0]);
        const size_t c1 = std::stoul(args[1]);
        const size_t r2 = std::stoul(args[2]);
        const size_t c2 = std::stoul(args[3]);

        if (r1 == r2 && c1 == c2) {
            return;
        }

        const auto [ pr, pc ] = find({ r1, c1 });
        const auto [ cr, cc ] = find({ r2, c2 });

        table[pr][pc] = table[pr][pc] == "" ? table[cr][cc] : table[pr][pc];
        parent[cr][cc] = { pr, pc };
    };

    Handler unmerge = [&] (const Args &args) {
        const size_t r = std::stoul(args[0]);
        const size_t c = std::stoul(args[1]);
        const auto [ pr, pc ] = find({ r, c });
        const std::string value = table[pr][pc];
        std::vector<Coordinate> to_unmerge;

        forEach([&] (size_t i, size_t j) {
            if (find({ r, c }) == find({ i, j })) {
                to_unmerge.push_back({ i, j });
            }
        });
        for (const auto [ i, j ]: to_unmerge) {
            parent[i][j] = { i, j };
            table[i][j] = "";
        }
        table[r][c] = value;
    };

    Handler print = [&] (const Args &args) {
        const size_t r = std::stoul(args[0]);
        const size_t c = std::stoul(args[1]);
        const auto [ pr, pc ] = find({ r, c });

        answer.push_back(table[pr][pc] == "" ? "EMPTY" : table[pr][pc]);
    };

    std::unordered_map<std::string, Handler> handlers = {
        { "UPDATE",  update },
        { "MERGE",   merge  },
        { "UNMERGE", unmerge },
        { "PRINT",   print },
    };

    for (const auto &command: commands) {
        const auto &splited = split(command);
        handlers[splited[0]](Args(std::next(splited.begin()), splited.end()));
    }

    return answer;
}

Share this post

N