[프로그래머스/파이썬] 2023 카카오 블라인드 리크루팅 표 병합

문제 해석

---

---

문제 풀이

---

merge와 unmerge 부분을 보고 바로 유니온 파인드(분리집합) 문제임을 알게되었다.

그런데 input을 tokenize할 필요가 있는 문자열 문제로 보여 C++이 아닌 파이썬으로 바꿔 풀게 되었다.

(C++에 string split을 구현할 수 있지만 구현 방법이  빠르게 떠오르지 않았다.)

단지 이 문제에서는 단순 분리집합 문제와 다르게 고려해야할 사항이 많았는데

 

1. MERGE 를 할 경우 같은 셀이면 무시, 둘 중 한 셀만 있을 땐 그 값만 유지, 모두 값이 있을 땐 왼쪽 윗 셀을 따른다.
2. UNMERGE 되면 지정한 위치가 그 값을 가지게 되고 다른 값들은 모두 초기화된다.
3. Input이 (1, 1) 부터 시작된다. (0, 0)으로 생각하면 틀린다.
4. MERGE 할 때 반대쪽 노드를 부모로 가지는 모든 노드를 갱신해주어야 한다.
   (참조: https://school.programmers.co.kr/questions/42579)

이외에는 구현이 문제인 문제였다. 50분안에 구현은 못했는데 구현 능력을 좀 기를 필요가 있어보인다.

---

def convertNum(x, y):
    result = 50 * (x - 1)
    return result + y

def update_cell(r, c, value, cell, parent):
    now = find_parent(convertNum(r,c), parent)
    cell[now] = value
    
def update_data(value1, value2, cell):
    for i in range(1, 2501):
        if cell[i] == value1:
            cell[i] = value2

def find_parent(val, parent):
    if val != parent[val]:
        parent[val] = find_parent(parent[val], parent)
    return parent[val]

def merge_data(r1, c1, r2, c2,cell, parent):
    parent2 = find_parent(convertNum(r2,c2), parent)
    parent1 = find_parent(convertNum(r1,c1), parent)
    if parent2 == parent1:
        return
    elif cell[parent1] == "EMPTY":
        parent[parent1] = parent2
        
        for i in range(1, 2501):
            if parent[i] == parent1:
                parent[i] = parent2
        return
    else:
        parent[parent2] = parent1
        
        for i in range(1, 2501):
            if parent[i] == parent2:
                parent[i] = parent1
        return

def unmerge_data(r1, c1, parent, cell):
    now = convertNum(r1,c1)
    p = parent[now]
    root = cell[p]

    nodes = []
    for i in range(1, 2501):
        if parent[i] == p:
            parent[i] = i
            cell[i] = "EMPTY"

    cell[now] = root

def solution(commands):
    answer = []
    cell = ["EMPTY" for i in range(2501)]
    parent = [j for j in range(2501)]
    
    for cmd in commands:
        prom = cmd.split(' ')
        if prom[0] == "UPDATE":
            if len(prom) == 4:
                update_cell(int(prom[1]), int(prom[2]), prom[3], cell, parent)
            else:
                update_data(prom[1], prom[2], cell)
        elif prom[0] == "MERGE":
            merge_data(int(prom[1]), int(prom[2]), int(prom[3]), int(prom[4]),cell, parent)
        elif prom[0] == "UNMERGE":
            unmerge_data(int(prom[1]), int(prom[2]), parent, cell)
        else:
            now = find_parent(convertNum(int(prom[1]), int(prom[2])), parent)
            answer.append(cell[now])
    return answer

---

느낀점: 문제가 신박하고 재밌었지만 내 구현능력에 한계를 느끼는 문제였다. 구현 실력을 조금 더 늘려야겠다.

문제링크:https://school.programmers.co.kr/learn/courses/30/lessons/150366

프로그래머스