[프로그래머스 / 파이썬] 2023 KAKAO BLIND RECRUITMENT 표 병합

프로그래머스에 존재하는 연습 문제이다.

 

문제 링크

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

프로그래머스

---

문제 해석

50 x 50 셀을 가진 표에 대해서 UPDATE, MERGE, UNMERGE, PRINT를 수행하고 PRINT 명령을 수행했을 때의 결과를 반환하는 문제이다.

주어진 조건을 잘 읽어가면 구현을 하면 되는 문제이다!

---

문제 풀이

주어진 조건을 잘 읽어가며 천천히 구현한다면 쉽게 풀 수 있는 문제이다.

영역을 합치는 머지와 초기화 하는 언머지의 명령을 쉽게 작동시키기 위해 50 x 50의 표에 각각 해당하는 키값을 할당해 주었다.

이후 딕셔너리로 store를 생성해 주었다. 표에 해당하는 키값을 store의 키값으로 활용하여 store의 밸류값에 실제값을 넣도록 구현했다.

 

즉 1, 2에 존재하는 키값이 3이라면 store[3]에 실제 값을 넣어주었다.

이 방법으로 구현하게 된다면 영역을 합칠 경우에는 같은 영역이 될 좌표에 같은 키값으로 변경만 해주면 되고,

언머지를 통해 영역을 초기화해야할 경우에는 부모 영역(최종적으로 값을 갖게될 좌표)을 제외한 모든 영역에 +1된 새로운 키값을 할당해주면 된다.

 

코드 주석을 참고하면 된다.

"MERGE r1 c1 r2 c2" 형태의 명령어를 입력 받았을 때 자손 좌표가 병합되어 있다면 병합된 자손값들을 모두 병합해주어야 한다.
문제를 잘못 해석해 처음에는 명령어에 입력된 좌표값만 바꾸어주었다..
이후 bfs를 통해 인접된 좌표를 바꾸어주었다..
두 경우 모두 아니였고, 자손이 되는 좌표와 병합된 모든 값들을 병합해주어야 한다!

---

문제 코드

# cells에 key값(index)을 적어 관리
cells = [[0] * 51 for _ in range(51)]
index = 1
# 1부터 키값 할당
for i in range(1, 51):
    for j in range(1, 51):
        cells[i][j] = index
        index += 1
store = {}

def change(r, c, value):
    store[cells[r][c]] = value

def get_target(key):
    targets = []
    for i in range(1, 51):
        for j in range(1, 51):
            if cells[i][j] == key: targets.append([i, j])
    return targets

def update(command):
    # print("update")
    # "UPDATE r c value" 형태
    if len(command) == 4:
        ud, r, c, value = command
        r, c = int(r), int(c)
        change(r, c, value)
    # "UPDATE value1 value2" 형태
    if len(command) == 3:
        ud, find_value, change_value = command
        for i in range(1, 51):
            for j in range(1, 51):
                if cells[i][j] in store and store[cells[i][j]] == find_value:
                    change(i, j, change_value)

def merge(command):
    # print("merge")
    # "MERGE r1 c1 r2 c2" 형태
    mg, r1, c1, r2, c2 = command
    r1, r2, c1, c2 = int(r1), int(r2), int(c1), int(c2)
    # 같은 좌표의 경우 무시
    if r1 == r2 and c1 == c2: return
    # 첫번째 값이 존재하면 첫번째 값으로 머지
    if cells[r1][c1] in store:
        # 두번째 키값을 가지는 좌표를 구하기
        targets = get_target(cells[r2][c2])
        for x, y in targets:
            cells[x][y] = cells[r1][c1]
    # 첫번째 값이 없다면 두번째 값으로 머지
    elif cells[r2][c2] in store:
        # 첫번째 키값을 가지는 좌표를 구하기
        targets = get_target(cells[r1][c1])
        for x, y in targets:
            cells[x][y] = cells[r2][c2]
    else:
        # 두번째 키값을 가지는 좌표를 구하기
        targets = get_target(cells[r2][c2])
        for x, y in targets:
            cells[x][y] = cells[r1][c1]
        

def ummerge(command):
    # print("unmerge")
    global index
    # "UNMERGE r c" 형태
    um, r, c = command
    r, c = int(r), int(c)
    # 완전 탐색하며 r,c와 같은 키값을 같는 값들을 찾아 키값을 새로 할당
    for i in range(1, 51):
        for j in range(1, 51):
            if i == r and j == c: continue
            if cells[i][j] == cells[r][c]:
                cells[i][j] = index
                index += 1

def print_cell(command):
    # print("print")
    pt, r, c = command
    r, c = int(r), int(c)
    
    if cells[r][c] in store:
        return store[cells[r][c]]
    else:
        return "EMPTY"
                
def solution(commands):
    answer = []
    for command in commands:
        command = command.split()
        if command[0] == "UPDATE": update(command)
        elif command[0] == "MERGE": merge(command)
        elif command[0] == "UNMERGE": ummerge(command)
        elif command[0] == "PRINT": 
            answer.append(print_cell(command))

    return answer

문제가 불친절한거 같아...