[Python 문제 풀이] 프로그래머스 '표 병합'

시키는 대로 꼼꼼하게 구현하자...

 

조건파악

50x50 표 위에서 문제를 풀게 된다.

첫번째 인덱스는 0이 아닌 1이다.

표 병합은 피상적으로 블럭을 합치는 게 아닐 수 있고 내부적으로 같은 값을 가리키기만 하면 된다.

(commands의 길이)<=1,000 이므로 시간복잡도는 크게 고려하지 않아도 될 것 같다.

접근

 문제의 핵심은 표를 병합하는 동작인 MERGE 커맨드이다. 두 개의 셀이, 혹은 두 개의 병합된 셀의 집합이 같은 값을 가리키도록 하면 된다. 나는 포인터를 이용해 한 셀이 또 다른 셀의 위치를 가리키도록 하고 값을 조회할 때는 포인터를 통해 조회하도록 했다. UNMERGE 동작시에는 반대로, 포함된 모든 셀의 포인터를 자기 자신을 가리키도록 초기화하면 된다. 이렇게 하면 나머지는 지시대로 구현하면 된다.

구현

def solution(commands):
    answer = []  # 결과를 저장할 리스트
    cell = [['EMPTY' for _ in range(51)] for _ in range(51)]  # 'EMPTY'로 초기화
    pointer = [[[i, j] for j in range(51)] for i in range(51)]  # 자기 자신을 가리키도록 초기화 
    
    def insert(r, c, value):
        rr, cc = pointer[r][c]  # 포인터에서 실제 위치(rr, cc) 가져옴
        cell[rr][cc] = value
        
    def update(value1, value2):
        for i in range(51):
            for j in range(51):
                if cell[i][j] == value1:
                    cell[i][j] = value2
                    
    def merge(r1, c1, r2, c2):
        rr1, cc1 = pointer[r1][c1]  # 1번 셀의 실제 위치
        rr2, cc2 = pointer[r2][c2]  # 2번 셀의 실제 위치
        value1, value2 = [cell[rr1][cc1], cell[rr2][cc2]]  # 각 셀 값을 가져옴
        cell[rr1][cc1] = value2 if value1 == 'EMPTY' else value1  # 값 변경
        for i in range(51):
            for j in range(51):
                if pointer[i][j] == [rr2, cc2]: # 2번 셀의 포인터를 1번 셀의 위치로 변경
                    pointer[i][j] = [rr1, cc1]  
        
    def unmerge(r, c):
        rr, cc = pointer[r][c]  # 실제 위치 가져옴
        value = cell[rr][cc]  # 셀 값 가져옴
        for i in range(51):
            for j in range(51):
                if pointer[i][j] == [rr, cc]:
                    pointer[i][j] = [i, j]  # 포인터 초기화
                    cell[i][j] = 'EMPTY'  # 값 초기화
        cell[r][c] = value  # 원래 위치의 셀 값을 복원
        
    def pprint(r, c):
        rr, cc = pointer[r][c]  # 포인터에서 실제 위치(rr, cc) 가져옴
        answer.append(cell[rr][cc])  # 셀 값 결과 리스트에 추가
        
    # 메인 루프
    for i in commands:
        a = i.split(' ')  # 공백을 기준으로 커맨드와 인자들을 분리
        if a[0] == 'UPDATE':
            if len(a) == 4:
                insert(int(a[1]), int(a[2]), a[3]) 
            else:
                update(a[1], a[2]) 
        elif a[0] == 'MERGE':
            merge(int(a[1]), int(a[2]), int(a[3]), int(a[4]))  
        elif a[0] == 'UNMERGE':
            unmerge(int(a[1]), int(a[2]))  
        else:
            pprint(int(a[1]), int(a[2]))  
            
    return answer