- Problem

2023 KAKAO BLIND RECRUITMENT 표 병합

값을 저장하는 이차원 배열과, 병합 상태를 저장하는 이차원 배열 두 개를 활용하면 쉽게 해결할 수 있다. 특별한 알고리즘은 요구한다기 보다는 구현에 가까운 문제다.

킹치만, 작년에 시험 볼 때 이 문제 못 품

문제로 주어지는 표의 위치가 0이 아닌 1부터 시작하기에 편의상 그리드의 크기를 51로 잡았다.

- 내 풀이

def solution(commands):
    def update(status):
        if len(status) == 3:
            update_one(status)
            return
        update_many(status)

    def update_one(status):
        y, x, val = status
        r, c = merged[int(y)][int(x)]
        grid[r][c] = val

    def update_many(status):
        val1, val2 = status
        for i in range(51):
            for j in range(51):
                if grid[i][j] == val1:
                    grid[i][j] = val2

    def get_valid_value(r1, c1, r2, c2):
        if grid[r1][c1] != 'EMPTY':
            return grid[r1][c1]
        elif grid[r2][c2] != "EMPTY":
            return grid[r2][c2]
        return 'EMPTY'

    def merge(status):
        y1, x1, y2, x2 = map(int, status)
        (r1, c1), (r2, c2) = merged[y1][x1], merged[y2][x2]
        val = get_valid_value(r1, c1, r2, c2)

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

        grid[r1][c1] = val

    def unmerge(status):
        x, y = map(int, status)
        r, c = merged[x][y]
        val = grid[r][c]

        for i in range(51):
            for j in range(51):
                if merged[i][j] == (r, c):
                    merged[i][j] = (i, j)
                    grid[i][j] = 'EMPTY'

        grid[x][y] = val

    def get_selected_value(status):
        y, x = map(int, status)
        r, c = merged[y][x]
        return grid[r][c]

    answer = []
    grid = [["EMPTY" for _ in range(51)] for _ in range(51)]
    merged = [[(i, j) for j in range(51)] for i in range(51)]

    for command in commands:

        operation, *status = command.split()
        if operation == 'UPDATE':
            update(status)

        elif operation == 'MERGE':
            merge(status)

        elif operation == 'UNMERGE':
            unmerge(status)

        elif operation == 'PRINT':
            val = get_selected_value(status)
            answer.append(val)

    return answer

• 시간 복잡도: O(N) (N: input으로 들어오는 command의 길이)
  • 만약, 문제에서 주어지는 그리드의 크기가 50*50이 아닌 가변적인 크기일 경우 가장 복잡한 연산인 이중 for문을 도는 merge, update_many 등은 M*N 의 시간을 가진다.
  • 그러나, 그리드의 크기는 항상 50*50 으로 고정되어 있기에, 가장 복잡한 연산은 O(2500) 즉, input 상관없이 일정한 상수 시간 O(1)을 가진다.
  • 따라서, 해당 문제의 시간 복잡도는 commands의 길이이 영향을 받게 된다.

• 공간 복잡도: O(1)
  - input의 크기와 상관없이 항상 고정된 51*51 사이즈의 이차원 배열 두 개를 가진다.

REF.

https://tech.kakao.com/2023/01/25/2023-kakao-recruitment-round-1/