[프로그래머스] 표 병합

문제

• 50x50 비어있는 표에 N개 명령어들을 차례로 실행한 후 결과 리턴하기
  • 1 <= N <= 1000
• 위에서 r번째, 왼쪽에서 c번째 위치를 (r, c) 라고 표현
• UPDATE
  • UPDATE r c value : (r, c) 위치 셀 값을 value 로 바꾸기
  • UPDATE value1 value2 : value1 값을 가진 모든 셀을 value2로 바꾸기
• MERGE r1 c1 r2 c2 : (r1, c1) 위치 셀과 (r2, c2) 위치 셀을 병합하기
  • 한 셀만 값을 가지면 해당 값을 가지게 되고, 둘 다 값을 가지면 (r1, c1) 의 값을 가지게 된다.
  • 이후 (r1, c1)과 (r2, c2) 중 어느 위치를 선택해도 병합된 셀로 접근하게 된다.
• UNMERGE r c
  • (r, c) 위치의 셀의 모든 병합을 해제
  • 병합 해제 전 셀이 값을 가지고 있었으면 (r, c) 위치의 셀이 그 값을 가지게 됨
• PRINT r c : (r, c) 위치의 셀 값을 출력
  • 비어있는 경우 "EMPTY" 출력

 

풀이 1

• table에 각 칸의 값 저장하고 비어있는 칸은 "EMPTY"로 채우기
• merge : 딕셔너리로 병합된 셀 관리하기. 
  • (c,d)를 (a,b)와 병합할 때 : merge[(c, d)] = (a, b) 
  • 만약 (c, d)가 이미 (e, f)와 병합되어 있는 셀인 경우, (e, f)로 병합된 모든 셀을 (a, b) 값으로 변경해주기
• unmerge : 딕셔너리에서 값 제거
  • (c, d) 를 병합해제할 때, 해당 값을 대표로 갖는 모든 key를 딕셔너리에서 제거하기

 

def solution(commands):
    table = [ ["EMPTY"]*51 for _ in range(51)]
    merge = dict()
    answer = []
    for command in commands:
        c = list(command.split())
        if c[0] == "UPDATE" :
            # 셀 한 칸 값 업데이트
            if len(c) == 4 :    
                r, c, v = int(c[1]), int(c[2]), c[3]
                # 병합된 셀인 경우 대표 셀만 변경
                if (r, c) in merge: 
                    r, c = merge[(r,c)]
                table[r][c] = v
            # value1 전체를 value2 로 업데이트
            else:
                _, v1, v2 = c
                for i in range(1, 51):
                    for j in range(1, 51):
                        if table[i][j] == v1:
                            table[i][j] = v2
        elif c[0] == "MERGE" :
            r1, c1, r2, c2 = int(c[1]), int(c[2]), int(c[3]), int(c[4])
            # 두 위치가 같은 경우 무시
            if r1 == r2 and c1 == c2 :  
                continue
            
            if (r1, c1) in merge:       # (r1, c1)이 병합된 경우
                r1, c1 = merge[(r1, c1)]
            if (r2, c2) in merge:       # (r2, c2)이 병합된 경우
                r2, c2 = merge[(r2, c2)]

            # 어떤 값으로 병합할지 정하기
            value = table[r2][c2] if table[r1][c1] == "EMPTY" and table[r2][c2] != "EMPTY" else table[r1][c1]
            table[r1][c1] = value

            # 병합하기
            if (r1, c1) not in merge:	# (r1, c1)이 병합되지 않은 경우
                merge[(r1, c1)] = (r1, c1)
            if (r2, c2) not in merge:   # (r2, c2) 병합되지 않은 경우
                merge[(r2, c2)] = (r1, c1)
            else:                       # (r2, c2) 병합된 경우, 대표 셀 (r1, c1)으로 변경
                for k, v in merge.items():
                    if v == (r2, c2) :
                        merge[k] = (r1, c1)
        elif c[0] == "UNMERGE" :
            r, c = int(c[1]), int(c[2])
            value = table[r][c]         # 현재 값
            if (r, c) in merge :
                x, y = merge[(r, c)]
                value = table[x][y]     # 병합된 경우 현재 값
                tmp = []
                for k, v in merge.items():
                    if v == (x, y):
                        table[k[0]][k[1]] = "EMPTY"
                        tmp.append(k)
                for k in tmp:
                    merge.pop(k)
            table[r][c] = value
        elif c[0] == "PRINT" :
            r, c = int(c[1]), int(c[2])
            if (r, c) in merge:
                r, c = merge[(r,c)]
            answer.append(table[r][c])
        

    return answer

 

 

풀이 2

• merge 관리를 딕셔너리가 아니라 유니온-파인드 형식으로 관리하기

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

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

def union_parent(p1, p2):
    p1 = find_parent(p1)
    p2 = find_parent(p2)

    if not table[p1] and table[p2] :  # b로 통합
        parent[p1] = p2
        table[p1] = table[p2]
    else:
        parent[p2] = p1
        table[p2] = table[p1]

def solution(commands):
    answer = []
    for command in commands:
        c = list(command.split())
        if c[0] == "UPDATE" :
            if len(c) == 4 :    # 셀 한 칸 값 업데이트   
                _, r, c, v = c
                r, c = int(r)-1, int(c)-1
                p = find_parent(r*50+c)
                table[p] = v
            else:               # value1 전체를 value2 로 업데이트
                _, v1, v2 = c
                for i in range(50*50):
                    if table[i] == v1 :
                        table[i] = v2
        elif c[0] == "MERGE" :
            r1, c1, r2, c2 = map(lambda x: int(x)-1, c[1:])
            
            x1 = r1 * 50 + c1
            x2 = r2 * 50 + c2
            if find_parent(x1) != find_parent(x2):
                union_parent(x1, x2)

        elif c[0] == "UNMERGE" :
            r, c = map(lambda x: int(x)-1, c[1:])
            p = find_parent(r*50+c)
            value = table[p]            # 현재 값
            
            nodes = []
            for i in range(50*50):
                if find_parent(i) == p :
                    nodes.append(i)
            for i in nodes:
                table[i] = ''
                parent[i] = i
            table[r*50+c] = value

        elif c[0] == "PRINT" :
            r, c = map(lambda x: int(x)-1, c[1:])
            p = find_parent(r*50+c)
            value = table[p] if table[p] else "EMPTY"
            answer.append(value)

    return answer

 

References

• 프로그래머스 Lv3 표 병합