[프로그래머스] 표 병합 (Python)

Problem : 코딩테스트 연습 - 표 병합 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

Status : Solved

Time : 01:07:33

 

---

 

문제 설명

 

당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

1. "UPDATE r c value"
   • (r, c) 위치의 셀을 선택합니다.
   • 선택한 셀의 값을 value로 바꿉니다.
2. "UPDATE value1 value2"
   • value1을 값으로 가지고 있는 모든 셀을 선택합니다.
   • 선택한 셀의 값을 value2로 바꿉니다.
3. "MERGE r1 c1 r2 c2"
   
   • (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
   • 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
   • 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
   • 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
   • 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
   • 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
4. "UNMERGE r c"
   • (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
   • 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
   • 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
5. "PRINT r c"
   • (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
   • 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

* 예시 설명은 링크를 참조해주세요!

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

입력 및 출력

 

제한사항

• 1 ≤ commands의 길이 ≤ 1,000
• commands의 각 원소는 아래 5가지 형태 중 하나입니다.
  1. "UPDATE r c value"
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
     • value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
  2. "UPDATE value1 value2"
     • value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
  3. "MERGE r1 c1 r2 c2"
     
     • r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  4. "UNMERGE r c"
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  5. "PRINT r c"
     
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
• commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.

 

입출력 예

commands	result
["UPDATE 1 1 menu", "UPDATE 1 2 category", "UPDATE 2 1 bibimbap", "UPDATE 2 2 korean", "UPDATE 2 3 rice", "UPDATE 3 1 ramyeon", "UPDATE 3 2 korean", "UPDATE 3 3 noodle", "UPDATE 3 4 instant", "UPDATE 4 1 pasta", "UPDATE 4 2 italian", "UPDATE 4 3 noodle", "MERGE 1 2 1 3", "MERGE 1 3 1 4", "UPDATE korean hansik", "UPDATE 1 3 group", "UNMERGE 1 4", "PRINT 1 3", "PRINT 1 4"]	["EMPTY", "group"]
["UPDATE 1 1 a", "UPDATE 1 2 b", "UPDATE 2 1 c", "UPDATE 2 2 d", "MERGE 1 1 1 2", "MERGE 2 2 2 1", "MERGE 2 1 1 1", "PRINT 1 1", "UNMERGE 2 2", "PRINT 1 1"]	["d", "EMPTY"]

 

 

---

 

풀이

대망의 2023 카카오 코테 6번째 문제. 요구하는 알고리즘 난이도는 상대적으로 낮으나, 구현의 어려움으로 승부하는 문제였다. 실제 기업에서 요구하는 문제 해결 능력을 테스트하는 느낌을 받았다. 4번 문제와 여러 모로 비교되는 문제였다.

2023.01.27 - [알고리즘 문제/프로그래머스] - [프로그래머스] 표현 가능한 이진트리 (Python)

[프로그래머스] 표현 가능한 이진트리 (Python)

 주어진 명령어에 따라 2차원 리스트(혹은 배열)을 관리하는 문제로, 특히 유념해야 할 것은 MERGE와 UNMERGE가 되시겠다. 효율적으로 셀을 '합치고' '분해하려면' Union-Find를 떠올려야 하는데, 이 Union-Find의 적용 순서만 주의하면 해결된다. 모든 명령어 처리 단계에 Find를 적용하면 실수를 줄일 수 있으며, UNMERGE의 경우 해당하는 parent를 가진 좌표를 전부 탐색한 이후 셀 값 변경을 수행하는 것이 parent 정보의 손실 없이 해결할 수 있었다.

UPDATE, PRINT와 같은 명령어는 배열의 최대 크기가 50x50이므로 완전 탐색으로도 허용 가능한 수준임을 밝혀 둔다.

 

풀이 코드

parent = [[(r, c) for c in range(51)] for r in range(51)]
cells = [['EMPTY']*51 for _ in range(51)]
result = []

def find(r, c) :
    if (r, c) == parent[r][c] :
        return parent[r][c]
    pr, pc = parent[r][c]
    parent[r][c] = find(pr, pc)
    return parent[r][c]

def union(r1, c1, r2, c2) :
    parent[r2][c2] = parent[r1][c1]

def UPDATE(r, c, msg) :
    pr, pc = find(r, c) 
    cells[pr][pc] = msg

def UPDATE_VAL(msg1, msg2):
    for r in range(51) :
        for c in range(51) :
            pr, pc = find(r, c)
            if cells[pr][pc] == msg1 :
                cells[pr][pc] = msg2
    
def MERGE(r1, c1, r2, c2) :
    r1, c1 = find(r1, c1)
    r2, c2 = find(r2, c2)
    
    if (r1, c1) == (r2, c2) :
        return
    if cells[r1][c1] != "EMPTY" :
        union(r1, c1, r2, c2)
    else :
        union(r2, c2, r1, c1)

def UNMERGE(r, c):
    pr, pc = find(r, c)
    msg = cells[pr][pc]
      
    merge_list = list()
    for ar in range(51) :
        for ac in range(51) :
            apr, apc = find(ar, ac)
            if (apr, apc) == (pr, pc) :
                merge_list.append((ar, ac))
                
    for ar, ac in merge_list :
        parent[ar][ac] = (ar, ac)
        cells[ar][ac] = "EMPTY" if (ar, ac) != (r, c) else msg
    
def PRINT(r, c) :
    pr, pc = find(r, c)
    result.append(cells[pr][pc])
        
def solution(commands):
    for command in commands :
        cmd, *arg = command.split()
        if cmd == "UPDATE" :
            if len(arg) == 3 :
                r, c, value = arg
                UPDATE(int(r), int(c), value)
            else :
                value1, value2 = arg
                UPDATE_VAL(value1, value2)
        elif cmd == "MERGE" :
            r1, c1, r2, c2 = map(int, arg)
            MERGE(r1, c1, r2, c2)
        elif cmd == "UNMERGE" :
            r, c = map(int, arg)
            UNMERGE(r, c)
        else :
            r, c = map(int, arg)
            PRINT(r, c)
            
    return result

풀이 완료!

이젠 마지막 7번 문제가 남았다. 코테 때도 제대로 풀질 못했던 문제인데... 과연 이번에는 풀어볼 수 있을지...