[프로그래머스] KAKAO 2023 BLIND RECRUITMENT - 표 병합

문제

프로그래머스

---

핵심

이 문제는 크게 위치별 업데이트, 단어별 업데이트, 병합, 병합 해제, 프린트 로 나뉘어져 있다.

업데이트의 경우 찾아서 바꿔주기만 하면 되므로 크게 문제가 안되는데 이 문제가 어려워진 이유는 병합에 있다. 

병합

각 셀이 병합이 된 이후에는 특정 셀을 업데이트할 시 해당 셀과 병합된 모든 셀을 동시에 업데이트 시켜야 했다. 

모든 셀을 하나처럼 움직여야 한다? -> 하나의 공통 조상을 가지고 있다? -> union-find!!

이 기능을 보자마자 생각난 것은 union-find! 업데이트 하려는 셀의 조상과 같은 조상을 가진 모든 셀들을 업데이트 시키면 된다고 생각했다.

위치별 업데이트

union-find까지 생각이 미치자 위치별 업데이트는 단순히 주어진 위치만 수정하는 건 잘못된 방식이었다. 해당 셀의 조상까지 모두 업데이트 시켜야 했다.

단어별 업데이트

이 부분은 나중에 다른 사람들 풀이를 보니까 되게 간단하게 풀었더라,, 그냥 모든 곳을 조회하고 바꿔야할 단어 있으면 바꾸는 식으로,,

근데 나는 알 수 없는 강박에 사로잡혀서 모든 곳을 단순히 조회하는건 시간초과날 확률이 높다고 생각했다. 고작 50*50인 사이즈임에도 불구하고...

 

내가 해결한 방법은 defaultdict()을 사용하는 것이다.

wordDict = defaultdict(set)

위치별 업데이트에서 단어가 추가되면 해당 단어를 key값으로 그 단어를 가지고 있는 셀의 인덱스를 set에 저장해놓고 추후 바꿔야할 단어를 해당 dictionary에서 찾아서 해당하는 셀들을 모두 업데이트하는 방식이다. 나름 잘 풀었다고 생각했는데 지금와서 생각해보면 쓸데없이 복잡하게 한 것 같기도..?

병합 해제

병합 해제는 위치별 업데이트와 마찬가지로 특정 셀과 조상들까지 모두 신경써주면 됐었다. 조상들의 조상을 다시 원상복구하고 값을 EMPTY로 만들어주고 본인만 원래 값이 있다면 그 값을 가지고 있으면 되는 간단한 문제였는데,, 내가 union-find를 생각하면서 union-find를 사용하지 않은게 복잡해진 패착이었던 것 같다.

---

코드

from collections import defaultdict

# 문제였던 것
# 1. 자식은 업데이트가 안됐었다.
# 2. defaultdict 미사용
# 3. if command[1].isDigit() 로 비교


def solution(commands):
    answer = []
    EMPTY = "EMPTY"

    table = [[EMPTY for _ in range(51)] for _ in range(51)]
    mergeTable = [[[(0, 0), (0, 0)] for _ in range(51)] for _ in range(51)]
    # defaultdict으로 초기회 하는게 좋다 타입 지정 ㄴㄴ
    wordDict = defaultdict(set)

    def findParent(row, col):
        while mergeTable[row][col][0] != (0, 0):
            row, col = mergeTable[row][col][0]
        return row, col

    def findChild(row, col):
        while mergeTable[row][col][1] != (0, 0):
            row, col = mergeTable[row][col][1]
        return row, col

    def initParent(row, col):
        while mergeTable[row][col][0] != (0, 0):
            tmpRow, tmpCol = row, col
            row, col = mergeTable[row][col][0]
            mergeTable[tmpRow][tmpCol][0] = (0, 0)

    def initChild(row, col):
        while mergeTable[row][col][1] != (0, 0):
            tmpRow, tmpCol = row, col
            row, col = mergeTable[row][col][1]
            mergeTable[tmpRow][tmpCol][1] = (0, 0)

    def changeParent(oldParentRow, oldParentCol, newParentRow, newParentCol):
        mergeTable[oldParentRow][oldParentCol][0] = (newParentRow, newParentCol)
        row, col = findChild(newParentRow, newParentCol)
        mergeTable[row][col][1] = (oldParentRow, oldParentCol)

    def updateWordDict(row, col, word):
        if (int(row), int(col)) in wordDict[table[int(row)][int(col)]]:
            wordDict[table[int(row)][int(col)]].remove((int(row), int(col)))
        wordDict[word].add((int(row), int(col)))

    def updateLoop(row, col, word, idx):
        while mergeTable[row][col][idx] != (0, 0):
            updateWordDict(row, col, word)
            table[row][col] = word
            row, col = mergeTable[row][col][idx]

        updateWordDict(row, col, word)
        table[row][col] = word

    def update(row, col, word):
        row, col = int(row), int(col)
        updateLoop(row, col, word, 0)
        updateLoop(row, col, word, 1)

    def updateToWord(target, word):
        if target == word:
            return

        updateList = list(wordDict[target])
        for row, col in updateList:
            update(row, col, word)

    def setMergeWord(r1, c1, r2, c2):
        if table[r1][c1] != EMPTY and table[r1][c2] != EMPTY:
            return table[r1][c1]
        elif table[r1][c1] != EMPTY:
            return table[r1][c1]
        elif table[r2][c2] != EMPTY:
            return table[r2][c2]
        else:
            return EMPTY

    def merge(r1, c1, r2, c2):
        if findParent(r1, c1) == findParent(r2, c2):
            return
        mergeWord = setMergeWord(r1, c1, r2, c2)
        newParentRow, newParentCol = findChild(r1, c1)
        oldParentRow, oldParentCol = findParent(r2, c2)
        changeParent(oldParentRow, oldParentCol, newParentRow, newParentCol)

        update(r1, c1, mergeWord)

    def unmerge(row, col):
        beforeWord = table[row][col]
        update(row, col, EMPTY)
        table[row][col] = beforeWord

        childRow, childCol = findChild(row, col)
        parentRow, parentCol = findParent(row, col)
        initParent(childRow, childCol)
        initChild(parentRow, parentCol)

    for command in commands:
        command = command.split()

        if command[0] == "UPDATE":
            # 처음엔 if command[1].isdigit(): 로 비교했다.
            # 하지만 value1에 숫자가 들어올 수도 있기에 split된 list의 길이로 판단해야 됨
            if len(command) == 3:
                updateToWord(command[1], command[2])
                continue
            update(command[1], command[2], command[3])
        elif command[0] == "MERGE":
            r1, c1, r2, c2 = map(int, command[1:5])
            merge(r1, c1, r2, c2)
        elif command[0] == "UNMERGE":
            row, col = map(int, command[1:3])
            unmerge(row, col)
        elif command[0] == "PRINT":
            answer.append(table[int(command[1])][int(command[2])])

    return answer

 

엉망진창인 내 코드.. 공개하기 부끄럽지만 나중엔 기록이 될 것이라 생각한다. 추후 리펙토링해봐야 겠다.

문제점

1. union-find를 한다고 해놓고 공통 조상으로 설정하는게 아니라 트리 형태로 이어지도록 설정했다. 그렇다보니 특정 셀을 업데이트 할 때, 자식은 업데이트가 되지 않았어서 자식에 대한 정보도 같이 넣어줘야 했었다...

 

2. 처음엔 defaultdict을 사용하지 않고 from typing import Dict을 사용해서 wordDict: Dict[str, set] = dict()이렇게 선언했더니 오류가 많았다..

-> 초기 타입 설정이 필요한 경우 초기값을 설정할 수 있는 defaultdict을 사용하자!!

 

3. 업데이트 시 해당 업데이트가 위치별 업데이트인지, 단어별 업데이트인지 파악하는 것이 필요했는데, 이 구분을 두번째 인자가 숫자인지 판단하는 걸로 해서 오류가 났었다. 문제 조건 중 "value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다." 를 보면 숫자도 단어별 업데이트에 들어갈 수 있다는 내용이 있다. 이를 간과해서 오류가 났었고 인자의 개수로 구분하는 방식으로 바꾸자 통과했다..! 문제 좀 꼼꼼히 읽자

 

4. 단순히 생각하자.. 크기가 작아 충분히 간단히 풀 수 있었던 문제임에도 너무 복잡하게 풀었다. 문제 조건을 더 잘 파악하고 더 간단히 풀어야 될 필요가 있다.