[프로그래머스]2023 Kakao Blind 공개채용 표 병합 파이썬

문제

당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

1. "UPDATE r c value"
   • (r, c) 위치의 셀을 선택합니다.
   • 선택한 셀의 값을 value로 바꿉니다.
2. "UPDATE value1 value2"
   • value1을 값으로 가지고 있는 모든 셀을 선택합니다.
   • 선택한 셀의 값을 value2로 바꿉니다.
3. "MERGE r1 c1 r2 c2"
   
   • (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
   • 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
   • 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
   • 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
   • 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
   • 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
4. "UNMERGE r c"
   • (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
   • 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
   • 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
5. "PRINT r c"
   • (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
   • 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.

UPDATE 1 1 menu	(1,1)에 "menu" 입력
UPDATE 1 2 category	(1,2)에 "category" 입력
UPDATE 2 1 bibimbap	(2,1)에 "bibimbap" 입력
UPDATE 2 2 korean	(2,2)에 "korean" 입력
UPDATE 2 3 rice	(2,3)에 "rice" 입력
UPDATE 3 1 ramyeon	(3,1)에 "ramyeon" 입력
UPDATE 3 2 korean	(3,2)에 "korean" 입력
UPDATE 3 3 noodle	(3,3)에 "noodle" 입력
UPDATE 3 4 instant	(3,4)에 "instant" 입력
UPDATE 4 1 pasta	(4,1)에 "pasta" 입력
UPDATE 4 2 italian	(4,2)에 "italian" 입력
UPDATE 4 3 noodle	(4,3)에 "noodle" 입력

위 명령어를 실행하면 아래 그림과 같은 상태가 됩니다.

아래는 MERGE 명령어를 실행하여 셀을 병합하는 예시입니다.

commands효과

MERGE 1 2 1 3	(1,2)와 (1,3) 병합
MERGE 1 3 1 4	(1,3)과 (1,4) 병합

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

병합한 셀은 "category" 값을 가지게 되며 (1,2), (1,3), (1,4) 중 어느 위치를 선택하더라도 접근할 수 있습니다.

아래는 UPDATE 명령어를 실행하여 셀의 값을 변경하는 예시입니다.

commands효과

UPDATE korean hansik	"korean"을 "hansik"으로 변경
UPDATE 1 3 group	(1,3) 위치의 셀 값을 "group"으로 변경

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.

commands효과

UNMERGE 1 4

셀 병합 해제 후 원래 값은 (1,4)가 가짐

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

해결

조금 신박한 구현 문제였다.

누구나 처음엔 위 그림처럼 배열을 그대로 만들고, 진행할 텐데 Merge, Unmerge 부분에서 많이 막혔을 것 같다. (심지어 시간제한 있는 코테니까)

 

나는 merge 되면 merge 된 부분은 모두 같은 값을 내뱉어야하고, merge된 부분들은 서로 어떤 셀과 병합되어있는지 알아야 한다는 점을 생각하여

배열을 board = [[["",[(y,x)]] for x in range(51)] for y in range(51)] 형식으로 만들었다. 즉, board[y][x][0]엔 그 셀에 해당하는 값이, board[y][x][1]에는 현재 본인의 좌표를 포함한 병합된 셀들의 좌표를 넣어놨다.

 

이렇게 병합된 셀들의 좌표를 넣어두면 Update 명령어나 Merge 명령어가 특정 셀에 불려도 병합되어 있는 모든 셀을 업데이트할 수 있다.

 

def solution(commands):
    answer = []

    board = [[["",[(y,x)]] for x in range(51)] for y in range(51)]

    for c in commands:
        li = c.split()
        
        ## 명령어 분기
        if li[0] == "UPDATE":
        	# 1번 경우
            if len(li) == 4:
            	# 해당 셀과 병합되어있는 모든 셀의 값을 변경해야한다.
                for r,c in board[int(li[1])][int(li[2])][1]:
                    board[r][c][0] = li[3]
            else:
            # 2번경우
                for y in range(1,51):
                    for x in range(1,51):
                   		셀들을 모두 돌며 value1값과 같다면 value2 값으로 변경한다. 	
                        if board[y][x][0] == li[1]:
                            board[y][x][0] = li[2]

        if li[0] == "MERGE":
        # 3번 경우
            r1,c1 = int(li[1]),int(li[2])
            r2,c2 = int(li[3]),int(li[4])
            
            # board[y][x][1]에는 해당 셀과 병합된 셀의 모든 정보가 들어있으므로, 
            # 두 셀의 병합된 셀을 더하고 집합으로 처리하면 병합될 모든 셀의 위치가 나온다.
            temp_li = list(set(board[r1][c1][1]+board[r2][c2][1]))
            
            # 병합되어있던 셀들의 병합 정보를 변경한다.
            for r,c in board[r1][c1][1]:
                board[r][c][1] = temp_li
            for r,c in board[r1][c1][1]:
                board[r][c][1]= temp_li
			
            # 이제 r1,c1과 r2,c2가 동일한 병합된 셀 정보를 갖고있다.
			# r1 c1에 value가 있었다면 병합된 셀의 정보를 모두 r1 c1의 value로 변경한다.
            # r1 c1에 값이 없고 r2 c2에 값이 있다면 r2 c2의 value로 변경한다.
            if board[r1][c1][0] != "":
                for r,c in board[r1][c1][1]:
                    board[r][c][0] = board[r1][c1][0]
            elif board[r2][c2][0] != "":
                for r,c in board[r2][c2][1]:
                    board[r][c][0] = board[r2][c2][0]

        if li[0] == "UNMERGE":
            # 4번 경우
            # 병합되어있던 셀들의 정보를 모두 초기화한다. 
            # value는 r,c 위치의 셀만 그대로 가지게 된다.
            for r,c in board[int(li[1])][int(li[2])][1]:
                if r == int(li[1]) and c == int(li[2]):
                    board[r][c][1] = [(r,c)]
                else:
                    board[r][c][1] = [(r,c)]
                    board[r][c][0] = ""
            
            
        if li[0] == "PRINT":
            r1,c1 = int(li[1]),int(li[2])
            if board[r1][c1][0] != "":
                answer.append(board[r1][c1][0])
            else:
                answer.append("EMPTY")
    return answer

 

주석을 잘 보면서 이해하기를 바란다. 

 

개인적인 체감 구현 난이도로는 그래도 풀만 했다고 생각한다. ( 2023 blind 카카오 공개채용 다른 코딩 테스트 문제에 비하면..)

실제로 이 문제와 나머지 쉬운 문제들만 다 맞혀도 1차 코딩테스트는 통과였다.

 

꼭!! 구현 문제는 연습해서 시간이 조금 걸리더라도 맞게끔 노력하도록 하자.

 

다른 언어로도 구현 문제를 조금 풀어봤지만.. 파이썬은 정말 사기인 것 같다🥲