2023 KAKAO BLIND RECRUITMENT 표 병합

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150366

파이썬 소스: https://bit.ly/4axcNSt

 

 이 문제는 유니온 파인드(Union-find)알고리즘을 사용해서 풀이하면 좀도 효율적으로 풀 수 있지만, 이중 루프를 사용해서 표의 셀을 모두 방문하는 방식으로도, 이 문제를 풀 수 있습니다.

표의크기가 50x50 이고, commands의 최대 길이는 1000 임으로, O(50 * 50 * 1000)입니다.

정리하면 O(2.5 * 10 ** 6)이 되구요, 시간안에 풀 수 있는 정도의 시간 복잡도입니다.

 

def solution(commands: List[str]):     MX = 51     map = [['EMPTY' for _ in range(MX)] for _ in range(MX)]     merged = [[(r, c) for c in range(MX)] for r in range(MX)]     answer = []

표의 최대 크기는 50 이고, commands에 입력되는 r, c 값은 1~50사이의 숫자이기 때문에, MX의 값이 51이 됩니다. 변수 MX를 사용한 이유는 디버깅할 때, map과 merged를 좀 작게 만들어서 브레이크 포인트를 잡았을 때, 쉽게 리스트의 값을 확인하려고, MX변수를 사용합니다.

셀에 어떤 값도 UPDATE되기 전에 해당 셀을 출력하면, ‘EMPTY’가 출력되어야 합니다. 따라서, map은 모두 ‘EMPTY’로 초기화 합니다.

리스트 merged는 MERGE, UNMERGE 명령어를 처리하기 위해서 사용하는 배열입니다.

merged = [[(r, c) for c in range(MX)] for r in range(MX)]

리스트 merged는 모두 (r, c)값으로 초기화 합니다.

merged[r][c] == (r, c) 라면, 머지가 되지 않은 셀이거나, value를 가리키고 있는 셀입니다.

명령어가 MERGE 1 1 1 2라고 하면

merged[1][2] = (1, 1) 저장해서, 1, 2는 1, 1에 머지된 셀이라고 표현합니다.

따라서, PRINT 1 2 명령어를 처리할 때,

merged[1][2] == (1, 2) 인지 확인하고, 아니라면

r, c = merged[1][2] 가 가리키고 있는 값을 r, c, 변수로 받아서

map[r][c]값을 출력해야 합니다.

 

for cmd in commands:         cmd = cmd.split(' ')

리스트 commands의 한 원소 cmd는 스트링입니다. 빈칸마다 하나의 스트링으로 나누기 위해서, split(‘ ‘)메서드를 사용합니다.

 

if cmd[0] == 'UPDATE' and len(cmd) == 4:             r, c, v = int(cmd[1]), int(cmd[2]), cmd[3]             if merged[r][c] == (r, c):                 map[r][c] = v             else:                 mr, mc = merged[r][c]                 map[mr][mc] = v

UPDATE r, c, v 형태의 UPDATE 명령어를 처리하는 코드입니다. cmd[1], cmd[2]는 map의 row, column을 가리키기 때문에, int()를 사용해서 숫자로 변환합니다.

map[r][c] == (r,c)이면 머지된 셀이 아니거나, 머지된 셀 중에서 값을 가리키고 있는 셀입니다.

따라서, map[r][c]에 v를 저장해서, UPDATE 명령어를 실행완료합니다.

 

elif cmd[0] == 'UPDATE' and len(cmd) == 3:             _, v1, v2 = cmd             for r in range(1, MX):                 for c in range(1, MX):                     if map[r][c] == v1:                         map[r][c] = v2

UPDATE v1, v2 형태의 UPDATE 명령어를 처리하는 코드입니다. 이중 루프로 map을 모두 확인하여, v1값을 가진 셀을 v2로 변경합니다.

 

elif cmd[0] == 'MERGE':             r1, c1, r2, c2 = int(cmd[1]), int(cmd[2]), int(cmd[3]), int(cmd[4])             to = merged[r1][c1]             fr = merged[r2][c2]             if map[to[0]][to[1]] == 'EMPTY':                 map[to[0]][to[1]] = map[fr[0]][fr[1]]             for r in range(1, MX):                 for c in range(1, MX):                     if merged[r][c] == fr:                         merged[r][c] = to

MERGE 명령어를 구현할 때는 아래 4가지 경우를 모두 처리할 수 있도록 구현해야 합니다.

1. 머지안된 셀과 머지안된 셀을 합친다

2. 머지된 셀과 머지안된 셀을 합친다.

3. 머지안된 셀과 머지된 셀을 합친다.

4. 머지된 셀과 머지된 셀을 합친다.

to = merged[r1][c1]

위와 같이 merged리스트에서 to 튜플을 가지고 오면, r1, c1이 머지된 셀이든, 머지 안된 셀이든, 항상 이 셀의 값은 map[to[0]][to[1]] 입니다.

if map[to[0]][to[1]] == 'EMPTY':                    map[to[0]][to[1]] = map[fr[0]][fr[1]]

map[r1][c1]에 값이 EMPTY인 경우만 map[r2][c2]값이 머지된 셀들의 값이 됩니다. 따라서 아래와 같이 코딩할 수 있습니다.

이제 셀을 머지 할 차례입니다.

for r in range(1, MX):                 for c in range(1, MX):                     if merged[r][c] == fr:                         merged[r][c] = to

r2, c2가 머지되지 않은 셀이면, merged에 (r2, c2)를 값을 가지는 원소는 merged[r2][c2]한 개 뿐일 것이구요, 머지된 셀이라면, merged의 다른 셀도 merged[r2][c2]와 같은 값을 가지고 있을 것입니다.

이중 루프로 merged의 모든 셀을 방문해서, fr튜플 값을 가지고 있다면, to튜플값으로 변경하여 MERGE 명령어 실행을 완료합니다.

 

elif cmd[0] == 'UNMERGE':             sr, sc = int(cmd[1]), int(cmd[2])             mr, mc = merged[sr][sc]             v = map[mr][mc]             for r in range(1, MX):                 for c in range(1, MX):                     if merged[r][c] == (mr, mc):                         merged[r][c] = (r, c)                         map[r][c] = 'EMPTY'             map[sr][sc] = v

sr, sc 셀과 머지된 셀들은 merged[sr][sc]의 튜플값을 가지고 있습니다. UNMERGE를 하기 전에, UNMERGE후에 map[sr][sc]가 가질 값을 구해서 v에 저장합니다.

이 중 루프를 사용해서, (mr, mc)튜플 값을 가지는 셀은 모두, UNMERGE하기 위해서 (r,c)튜플로 변경하고, map[r][c]도 ‘EMPTY’로 변경합니다.

마지막으로 map[sr][src]의 셀이 v값을 가지도록 합니다.

 

마지막으로 PRINT명령어를 구현해 보겠습니다.

elif cmd[0] == 'PRINT':             r, c = int(cmd[1]), int(cmd[2])             if merged[r][c] != (r, c):                 mr, mc = merged[r][c]                 answer.append(map[mr][mc])             else:                 answer.append(map[r][c])

merged[r][c] != (r, c): 성립하면, 머지된 셀이므로, merged[r][c]에 저장되어 있는 튜플의 mr, mc 값을 가지고 map[mr][mc] 참조하여, 해당 셀의 값을 구할 수 있습니다.

머지되지 않은 셀이라면, map[r][c]에서 바로 해당 셀의 값을 구할 수 있습니다.

 

전체 코드는 아래와 같습니다.

궁금한 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

from typing import List def solution(commands: List[str]):     MX = 51     map = [['EMPTY' for _ in range(MX)] for _ in range(MX)]     merged = [[(r, c) for c in range(MX)] for r in range(MX)]     answer = []     for cmd in commands:         cmd = cmd.split(' ')         if cmd[0] == 'UPDATE' and len(cmd) == 4:             r, c, v = int(cmd[1]), int(cmd[2]), cmd[3]             if merged[r][c] == (r, c):                 map[r][c] = v             else:                 mr, mc = merged[r][c]                 map[mr][mc] = v         elif cmd[0] == 'UPDATE' and len(cmd) == 3:             _, v1, v2 = cmd             for r in range(1, MX):                 for c in range(1, MX):                     if map[r][c] == v1:                         map[r][c] = v2         elif cmd[0] == 'MERGE':             r1, c1, r2, c2 = int(cmd[1]), int(cmd[2]), int(cmd[3]), int(cmd[4])             to = merged[r1][c1]             fr = merged[r2][c2]             if map[to[0]][to[1]] == 'EMPTY':                 map[to[0]][to[1]] = map[fr[0]][fr[1]]             for r in range(1, MX):                 for c in range(1, MX):                     if merged[r][c] == fr:                         merged[r][c] = to         elif cmd[0] == 'UNMERGE':             sr, sc = int(cmd[1]), int(cmd[2])             mr, mc = merged[sr][sc]             v = map[mr][mc]             for r in range(1, MX):                 for c in range(1, MX):                     if merged[r][c] == (mr, mc):                         merged[r][c] = (r, c)                         map[r][c] = 'EMPTY'             map[sr][sc] = v         elif cmd[0] == 'PRINT':             r, c = int(cmd[1]), int(cmd[2])             if merged[r][c] != (r, c):                 mr, mc = merged[r][c]                 answer.append(map[mr][mc])             else:                 answer.append(map[r][c])     return answer