[프로그래머스 LV.3] 표 병합 (파이썬/python)

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

프로그래머스

 

MERGE 를 다루는게 조금 까다로웠다.

사실 표의 최대 사이즈가 50 * 50 밖에 안돼서 조금 로우하게 코드를 써도 됐을것 같은데

이래저래 생각이 많았다.

 

서로 병합도된 노드 라는것을 어떻게 표시를 할까를 고민했는데

아래 코드는 시간초과가 나는 코드..

 

1. 풀이에 실패한코드(실패)

def solution(commands):
    answer = []
    excel_list = [[None for i in range(51)] for j in range(51)]
    merge_list = [[[[j, i]] for i in range(51)] for j in range(51)]

    UPDATE = "UPDATE"
    MERGE = "MERGE"
    UNMERGE = "UNMERGE"
    PRINT = "PRINT"

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

        if command_list[0] == UPDATE and len(command_list) == 4:
            r, c, value = command_list[1:]

            for target in merge_list[int(r)][int(c)]:
                excel_list[target[0]][target[1]] = value

        elif command_list[0] == UPDATE:
            v1, v2 = command_list[1:]

            for i in range(len(excel_list)):
                for j in range(len(excel_list[0])):
                    if excel_list[i][j] == v1:
                        excel_list[i][j] = v2

        elif command_list[0] == MERGE:
            r1, c1, r2, c2 = command_list[1:]

            if merge_list[int(r1)][int(c1)] in [int(r2), int(c2)]:
                continue

            target_value_i = int(r1) if excel_list[int(r1)][int(c1)] else int(r2)
            target_value_j = int(c1) if excel_list[int(r1)][int(c1)] else int(c2)

            first_list = merge_list[int(r1)][int(c1)][:]
            second_list = merge_list[int(r2)][int(c2)][:]
            for target in first_list:
                merge_list[target[0]][target[1]] += second_list[:]
                excel_list[target[0]][target[1]] = excel_list[target_value_i][target_value_j]

            for target in second_list:
                merge_list[target[0]][target[1]] += first_list[:]
                excel_list[target[0]][target[1]] = excel_list[target_value_i][target_value_j]

        elif command_list[0] == UNMERGE:
            r, c = command_list[1:]

            target_list = merge_list[int(r)][int(c)][:]
            for target in target_list:
                merge_list[target[0]][target[1]] = [[target[0], target[1]]]
                if target[0] != int(r) or target[1] != int(c):
                    excel_list[target[0]][target[1]] = None

        elif command_list[0] == PRINT:
            r, c = command_list[1:]

            if not excel_list[int(r)][int(c)]:
                answer.append("EMPTY")
            else:
                answer.append(excel_list[int(r)][int(c)])
    return answer

 

 

 

 

 

2. 유니온파인드를 사용해서 푼 코드(성공)

def find(r: int, c: int) -> list:
    if parent[r][c] != [r, c]:
        next_r, next_c = parent[r][c]
        parent[r][c] = find(next_r, next_c)

    return parent[r][c]


def update1(r: int, c: int, value: str) -> None:
    root = find(r, c)

    for i in range(51):
        for j in range(51):
            if find(i, j) == root:
                excel_list[i][j] = value


def update2(v1: str, v2: str) -> None:
    for i in range(51):
        for j in range(51):
            if excel_list[i][j] == v1:
                excel_list[i][j] = v2


def merge(r1: int, c1: int, r2: int, c2: int) -> None:
    r1, c1 = find(r1, c1)
    r2, c2 = find(r2, c2)

    if [r1, c1] == [r2, c2]:
        return
    parent[r2][c2] = [r1, c1]
    value = excel_list[r1][c1] if excel_list[r1][c1] else excel_list[r2][c2]
    update1(r1, c1, value)


def un_merge(r: int, c: int) -> None:
    root = find(r, c)
    value = excel_list[root[0]][root[1]]

    un_merged_list = []

    for i in range(51):
        for j in range(51):
            if find(i, j) == root:
                un_merged_list.append([i, j])

    for un_merged in un_merged_list:
        un_r, un_c = un_merged

        parent[un_r][un_c] = [un_r, un_c]
        excel_list[un_r][un_c] = None

    excel_list[r][c] = value


def printer(r: int, c: int):
    answer.append(excel_list[r][c] if excel_list[r][c] else "EMPTY")


def solution(commands):
    global parent
    global excel_list
    global answer
    answer = []
    excel_list = [[None for i in range(51)] for j in range(51)]
    parent = [[[r, c] for c in range(51)] for r in range(51)]

    UPDATE = "UPDATE"
    MERGE = "MERGE"
    UNMERGE = "UNMERGE"
    PRINT = "PRINT"

    for command in commands:
        # print("11111")
        # for i in excel_list:
        #     print(i)
        command = command.split(" ")
        cmd, value = command[0], command[1:]

        if cmd == UPDATE and len(value) == 3:
            update1(int(value[0]), int(value[1]), value[2])
        elif cmd == UPDATE:
            update2(value[0], value[1])
        elif cmd == MERGE:
            r1, c1, r2, c2 = map(int, value)
            merge(r1, c1, r2, c2)
        elif cmd == UNMERGE:
            r, c = map(int, value)
            un_merge(r, c)
        elif cmd == PRINT:
            r, c = map(int, value)
            printer(r, c)
        
     return answer