[프로그래머스] 2023 Kakao Blind Recruitment : 표병합

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

프로그래머스

📄 문제개요

• 해당 문제는 주어진 조건에따라서 명령을 수행하는 구현 문제이다.
• 주어진 문제의 요구사항에는 서로소 집합 자료구조를 사용하여 해결 해야한다.
• 표가 주어졌을때, 병합하고, 값을 변경하고, 병합을 해제하고 원하는 값을 출력한다.

🤔 문제분석

• 표는 최대 50, 50 임으로, (50,50) 테이블을 만든다.
• 특정위치의 첫번째 인덱스는 표의 값을 표현하고, 두번째 인덱스는 그룹상태를 알려주는 자료구조를 잡는다.
• 업데이트 함수는 특정 위치의 셀을 Value로 바꾼다.
• 병합 함수는 특정위치와 또다른 특정위치와 병합을 한다 ( 집합 자료형을 사용하여 | 연산하여 유니온 하였다)
• 병합 해제는 특정위치와 또다른 특정위츠를 병합 해제 시킨다. ( 집합 자료형을 자기자신으로 다시 바꾼다 )

📝 의사코드

1. 명령어를 순회한다.
2. 주어진 조건에따라서 함수를 실행시킨다.

• 여기서 중요한건 Merge 함수인데, Merge 함수는 각각의 모든 그룹들을 모두 합쳐준다. 그리고 그 합친 값들을 주어진 조건에 따라 잘 바꿔주면 된다.

💻 코드

MAX_SIZE = 50
table = [[[] for _ in range(MAX_SIZE)] for _ in range(MAX_SIZE)]

for r in range(MAX_SIZE):
    for c in range(MAX_SIZE):
        table[r][c].append('EMPTY')
        table[r][c].append(set())
        table[r][c][1].add(((r, c)))

def update(r, c, value):
    for g_r, g_c in table[r][c][1]:
        table[g_r][g_c][0] = value
        
def update_all(value1, value2):
    for r in range(MAX_SIZE):
        for c in range(MAX_SIZE):
            if table[r][c][0] == value1:
                table[r][c][0] = value2
                
def merge(r1, c1, r2, c2):
    if table[r1][c1][1] == table[r2][c2][1]:
        return
    
    unioned_table = table[r1][c1][1] | table[r2][c2][1]
    
    for g_r, g_c in table[r1][c1][1]:
        table[g_r][g_c][1] = unioned_table
        
    for g_r, g_c in table[r2][c2][1]:
        table[g_r][g_c][1] = unioned_table
        
    
    if table[r1][c1][0] == 'EMPTY':
        for g_r, g_c in table[r1][c1][1]:
            table[g_r][g_c][0] =  table[r2][c2][0]
    else:
        for g_r, g_c in table[r2][c2][1]:
            table[g_r][g_c][0] =  table[r1][c1][0]
            
def unmerge(r1, c1):
    for g_r, g_c in table[r1][c1][1]:
        if (g_r, g_c) != (r1, c1):
            table[g_r][g_c][1] = set()
            table[g_r][g_c][1].add(((g_r, g_c)))
            table[g_r][g_c][0] = 'EMPTY'
    
    table[r1][c1][1] = set()
    table[r1][c1][1].add(((r1, c1)))
    
def cmd_print(r1, c1):
    return table[r1][c1][0]

def solution(commands):
    answer = []
    for command in commands:
        command = command.split(' ')
        
        if command[0] == 'UPDATE':
            if len(command) == 4:
                r1, c1, value = command[1], command[2], command[3]
                r1, c1 = int(r1)-1, int(c1) -1
                update(r1, c1, value)
            else:
                value1, value2 = command[1], command[2]
                update_all(value1, value2)
        elif command[0] == 'MERGE':
            r1, c1, r2, c2 = command[1], command[2], command[3], command[4]
            r1, c1, r2, c2 = int(r1)-1, int(c1) -1, int(r2)-1, int(c2) -1
            merge(r1, c1, r2 ,c2)
        elif command[0] == 'UNMERGE':
            r1, c1 = command[1], command[2]
            r1, c1 = int(r1)-1, int(c1) -1
            unmerge(r1, c1)
        elif command[0] == 'PRINT':
            r1, c1 = command[1], command[2]
            r1, c1 = int(r1)-1, int(c1) -1
            answer.append(cmd_print(r1, c1))
            
    return answer

🎯 피드백 및 개선사항

• 해당 문제는 구현문제로, 문제만 정확하게 이해하면 주어진 조건에따라서 쉽게 풀 수 있는 문제이다.

❓다른사람은 어떻게 풀었을까?

• 해당문제는 50x50이고, 명령수가 적은 수이기때문에 문제를 최적화 하지 않고 빠르게 문제를 푸는데에 집중 했다.
• 1차원 배열을 사용하였고, 유니온 - 파인드로 문제를 해결 하신분이 있다.
• 메모리복잡도, 시간복잡도에서 훨씬 빠르다.

values = ['' for _ in range(50 * 50)]
parent = [i for i in range(50 * 50)]

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(x1, x2):
    root1 = find(x1)
    root2 = find(x2)

    if not values[root1] and values[root2]:
        parent[root1] = root2
        values[root1] = values[root2]
    else:
        parent[root2] = root1
        values[root2] = values[root1]

def solution(commands):
    answer = []

    for command in commands:
        command = list(command.split())
        if command[0] == 'UPDATE':
            if len(command) == 4:   # r, c의 root value만을 바꿔준다.
                r, c, value = command[1:]
                r, c = int(r) - 1, int(c) - 1
                x = r * 50 + c
                rootx = find(x)
                values[rootx] = value

            else: # value1을 모두 찾아, value2로 바꿔준다.
                value1, value2 = command[1:]
                for i in range(50 * 50):
                    if values[i] == value1:
                        values[i] = value2

        elif command[0] == 'MERGE':
            r1, c1, r2, c2 = map(lambda x: int(x) - 1, command[1:])

            x1 = r1 * 50 + c1
            x2 = r2 * 50 + c2
            if parent[x1] != parent[x2]:
                union(x1, x2)

        elif command[0] == 'UNMERGE':
            r, c = map(lambda x: int(x) - 1, command[1:])
            x = r * 50 + c
            rootx = find(x)
            valuex = values[rootx]

            nodes = []
            for i in range(50 * 50):
                if find(i) == rootx:
                    nodes.append(i)

            for node in nodes:
                values[node] = ''
                parent[node] = node

            values[x] = valuex

        elif command[0] == 'PRINT':
            r, c = map(lambda x: int(x) - 1, command[1:])
            x = r * 50 + c
            rootx = find(x)

            if not values[rootx]:
                answer.append('EMPTY')
            else:
                answer.append(values[rootx])

    return answer