[프로그래머스]표 병합

문제

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

소스코드

def solution(commands):
    answer = []
    val_table = [["EMPTY" for _ in range(51)] for _ in range(51)]
    addr_table = [[(r,c) for c in range(51)] for r in range(51)]


    def update_val(v1, v2):
        for i in range(51):
            for j in range(51):
                if val_table[i][j] == v1:
                    val_table[i][j] = v2

    def update_addr(ix, iy, v):
        x, y = int(ix), int(iy)
        r, c = addr_table[x][y]
        val_table[r][c] = v


    def merge(ix1, iy1, ix2, iy2):
        x1, y1, x2, y2 = int(ix1), int(iy1), int(ix2), int(iy2)
        
        r1,c1 = addr_table[x1][y1]
        r2,c2 = addr_table[x2][y2]
        
        if val_table[r1][c1] == "EMPTY":
            val_table[r1][c1] = val_table[r2][c2]

        for i in range(51):
            for j in range(51):
                if addr_table[i][j] == (r2,c2):
                    addr_table[i][j] = (r1,c1)

    def unmerge(ix, iy):
        x, y = int(ix), int(iy)
        r,c = addr_table[x][y]
        tmp = val_table[r][c]

        for i in range(51):
            for j in range(51):
                if addr_table[i][j] == (r,c):
                    addr_table[i][j] = (i,j)
                    val_table[i][j] = "EMPTY"

        val_table[x][y] = tmp

    def print(ix,iy):
        x, y = int(ix), int(iy)
        r, c = addr_table[x][y]
        return val_table[r][c]

    for command in commands:

        c = command.split()

        if c[0] == "UPDATE":
            if len(c) == 4:
                update_addr(c[1], c[2], c[3])
            else:
                update_val(c[1], c[2])
        elif c[0] == "MERGE":
            merge(c[1], c[2], c[3], c[4])
        elif c[0] == "UNMERGE":
            unmerge(c[1], c[2])
        elif c[0] == "PRINT":
            answer.append(print(c[1],c[2]))

    return answer

설명

구현으로 문제를 풀어봤다. 검색해보니 union-find로 많이 풀었다. 근데 내가 푼것도 풀어보면 union-find 기반인 것 같다.

빡구현인데 거의 2일동안 풀었다ㅠ.ㅠ

 

변수 초기화

1. 값을 저장할 이차원 배열
2. 주소값을 저장할 이차원 배열(merge시 사용)

함수 로직

• 값을 변경하는 함수
  • 값 배열을 탐색해서 v1이면 v2로 수정해준다.
• 특정 주소의 값을 변경해주는 함수
  • 입력받은 주소가 현재 어딜 향하는지 주소 배열을 통해 추출한다.
  • 추출한 주소 배열의 주소의 값 배열에 변경해준다.
• 병합 함수
  • 1번째 주소의 값이 비어있다면 2번의 값을 넣어준다
  • 문제에 둘이 같으면 체크하지 않는다라고 되어 있는데 굳이 체크 안해줘도 된다.
  • 반복문을 돌면서 2번의 주소값이 되어 있는 부분을 모두 1번으로 변경한다.
• 병합 해제 함수
  • 현재 주어진 주소의 원주소를 찾는다
  • 반복문을 돌면서 원주소랑 일치하는 주소들을 다 자기 자신으로 변경한다
  • 값도 다 empty로 변경해준다
  • 현재 주어진 주소에만 기존 값을 넣어준다
• 출력 함수
  • 주어진 주소의 원주소를 찾는다
  • 원주소의 값을 출력한다

 

후기

구현으로 될거같아서 오기로 구현으로 푼 문제 카카오테크 블로그에도 이렇게 풀었다

다음번에 유니온 파인드로 다시 풀어보자