표 병합 [Lv. 3]

프로그래머스

 

50 * 50 크기의 셀이 있을 때

셀 UPDATE, MERGE, UNMERGE, PRINT 함수를 만드는 문제입니다.

 

풀이 방법

문제의 핵심은 셀 병합과 병합해제를 어떻게 구현하느냐에 있습니다.

저는 union - find 알고리즘을 이용하여 간단하게 풀어보았습니다.

 

struct cell
{
    int parent;
    string value = "EMPTY";
};

vector<cell> table;

table.resize(50 * 50);
for (int i = 0; i < table.size(); i++)
    table[i].parent = i;

우선 cell을 구조체로 만들어주었고 병합될때 부모 index를 가질 수 있게 parent 변수를 추가 했습니다.

table의 경우에는 2차원 배열로 만드는 것이 아닌 1차원 배열로 만들어 인덱싱을 쉽게 하였습니다.

반복문은 union-find 알고리즘을 위한 parent를 자기 자신으로 초기화하는 코드입니다.

 

vector<string> stoc(string str)
{
    vector<string> r;
    string t;
    for (auto c : str)
    {
        if (c == ' ')
        {
            r.push_back(t);
            t = "";
            continue;
        }
        t += c;
    }
    r.push_back(t);
    
    return r;
}

Command를 쉽게 관리하기 위해 strirng을 vector로 분리하는 코드를 만들었습니다.

string(UPDATE 1 2 Hello) -> vector<string>{UPDATE, 1, 2, Hello}

 

int Find(int a)
{
    if (a == table[a].parent)
        return a;
    
     return table[a].parent = Find(table[a].parent);
}

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    
    if (table[a].value == "EMPTY" && table[b].value != "EMPTY")
        table[a].parent = b;
    else
        table[b].parent = a;
}

Union-Find 함수 구현부분 입니다.

Find는 기존 방식과 동일하고 Union의 경우는 해당 문제에 맞게 변형했습니다.

 

for (string s : commands)
{
    vector<string> cmd = stoc(s);

    if (cmd[0] == "UPDATE")
    {
        if (cmd.size() == 4)
        {
            int r = stoi(cmd[1]) - 1;
            int c = stoi(cmd[2]) - 1;
            int idx = Find(r * 50 + c);

            table[idx].value = cmd[3];
        }
        else
        {
            for (cell& c : table)
            {
                if (c.value == cmd[1])
                    c.value = cmd[2];
            }
        }
    }
}

명령어가 UPDATE일 경우의 코드 입니다.

stoi 함수를 이용하여 string을 숫자로 변경해주었고

 1 ~ 50 사이의 수를 0~ 49의 인덱스 번호에 맞게 바꿔주었습니다.

 

else if (cmd[0] == "MERGE")
{
    int r1 = stoi(cmd[1]) - 1;
    int c1 = stoi(cmd[2]) - 1;

    int r2 = stoi(cmd[3]) - 1;
    int c2 = stoi(cmd[4]) - 1;

    int idx1 = r1 * 50 + c1;
    int idx2 = r2 * 50 + c2;
    Union(idx1, idx2);

}

병합 합수는 Union 함수 호출로 해결이 가능합니다.

 

else if (cmd[0] == "UNMERGE")
{
    int r = stoi(cmd[1]) - 1;
    int c = stoi(cmd[2]) - 1;

    int idx = r * 50 + c;
    int root = Find(idx);
    string value = table[root].value;

    vector<int> target;
    for (int i = 0; i < table.size(); i++)
    {
        if (Find(i) == root)
        {
            target.push_back(i);
        }
    }

    for (int i : target)
    {
        table[i].parent = i;
        table[i].value = "EMPTY";
    } 

    table[idx].parent = idx;
    table[idx].value = value;

}

UNMERGE에서는 같은 root를 가진 cell을 모두 찾아주었습니다.

이 때 target에 넣어주기만 하고 후에 value와 parent를 초기화 해주고 있는데

찾자 마자 바로 초기화 해주면 해당 인덱스를 부모로 가지고 있던 cell은 찾지 못하는 문제가 발생하기에

후에 처리하는 방식으로 코드를 만들었습니다.

 

    else if (cmd[0] == "PRINT")
    {
        int r = stoi(cmd[1]) - 1;
        int c = stoi(cmd[2]) - 1;
        int idx = Find(r * 50 + c);
        answer.push_back(table[idx].value);
    }

PRINT 명령어는 부모 인덱스의 cell에 접근하여 출력하게 하였습니다.

 

 

전체 코드

#include <string>
#include <vector>

using namespace std;

struct cell
{
    int parent;
    string value = "EMPTY";
};

vector<string> stoc(string str);
int Find(int a);
void Union(int a, int b);

vector<cell> table;

vector<string> solution(vector<string> commands) {
    vector<string> answer;
    table.resize(50 * 50);
    for (int i = 0; i < table.size(); i++)
        table[i].parent = i;
    
    for (string s : commands)
    {
        vector<string> cmd = stoc(s);
        
        if (cmd[0] == "UPDATE")
        {
            if (cmd.size() == 4)
            {                
                int r = stoi(cmd[1]) - 1;
                int c = stoi(cmd[2]) - 1;
                int idx = Find(r * 50 + c);
                
                table[idx].value = cmd[3];
            }
            else
            {
                for (cell& c : table)
                {
                    if (c.value == cmd[1])
                        c.value = cmd[2];
                }
            }
        }
        else if (cmd[0] == "MERGE")
        {
            int r1 = stoi(cmd[1]) - 1;
            int c1 = stoi(cmd[2]) - 1;
            
            int r2 = stoi(cmd[3]) - 1;
            int c2 = stoi(cmd[4]) - 1;
            
            int idx1 = r1 * 50 + c1;
            int idx2 = r2 * 50 + c2;
            Union(idx1, idx2);
            
        }
        else if (cmd[0] == "UNMERGE")
        {
            int r = stoi(cmd[1]) - 1;
            int c = stoi(cmd[2]) - 1;
            
            int idx = r * 50 + c;
            int root = Find(idx);
            string value = table[root].value;
            
            vector<int> target;
            for (int i = 0; i < table.size(); i++)
            {
                if (Find(i) == root)
                {
                    target.push_back(i);
                }
            }
            
            for (int i : target)
            {
                table[i].parent = i;
                table[i].value = "EMPTY";
            } 
            
            table[idx].parent = idx;
            table[idx].value = value;
            
        }
        else if (cmd[0] == "PRINT")
        {
            int r = stoi(cmd[1]) - 1;
            int c = stoi(cmd[2]) - 1;
            int idx = Find(r * 50 + c);
            answer.push_back(table[idx].value);
        }
    }
    
    return answer;
}

int Find(int a)
{
    if (a == table[a].parent)
        return a;
    
     return table[a].parent = Find(table[a].parent);
}

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    
    if (table[a].value == "EMPTY" && table[b].value != "EMPTY")
        table[a].parent = b;
    else
        table[b].parent = a;
}

vector<string> stoc(string str)
{
    vector<string> r;
    string t;
    for (auto c : str)
    {
        if (c == ' ')
        {
            r.push_back(t);
            t = "";
            continue;
        }
        t += c;
    }
    r.push_back(t);
    
    return r;
}