[2023 KAKAO BLIND RECRUITMENT] - 표 병합 (python)

김준엽·2023년 2월 1일
1

알고리즘

목록 보기
5/5
post-thumbnail

문제

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

문제 설명

당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 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 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.

commands 효과
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" 입력

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

1-1.png

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

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

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

1-2.png

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

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

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

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

1-3.png

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

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

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

1-4.png

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


제한사항
  • 1 ≤ commands의 길이 ≤ 1,000
  • commands의 각 원소는 아래 5가지 형태 중 하나입니다.
    1. "UPDATE r c value"
      • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
      • value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
    2. "UPDATE value1 value2"
      • value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
    3. "MERGE r1 c1 r2 c2"
      • r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
    4. "UNMERGE r c"
      • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
    5. "PRINT r c"
      • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  • commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.

접근 방식

처음 이 문제를 시험날 봤을 때 쉬워보였다.
단순 구현 문제인것 같았으며, 단순하기 삽입, 출력만 하는 듯한 문제였기 때문이다.
그런데 MERGE의 존재 하나로 너무나도 어렵게 느껴졌던 문제였다.

그런데 카카오 테크 블로그의 해설은 정말 단순 구현 이었다.
문제의 핵심 해결 포인트는

  1. 각 표의 인덱스를 관리하는 merge 자료구조를 하나 둔다.
  2. 각 표의 값을 관리하는 content 자료구조를 하나 둔다.

이게 끝이다..
그냥 각 표의 값에 접근할 때는 인덱스를 관리하는 merge를 거쳐서 접근하도록만 설계하면 끝나는 문제였다...

이 문제의 해결 방식은 카카오 테크 블로그에 설명을 그대로 따라가면 풀리는 문제이므로, 해당 블로그를 참고하면 된다.

  1. “UPDATE r c value”
    merged[r][c]의 값 (x, y)를 찾아 content[x][y]의 값을 value로 변경합니다.

  2. “UPDATE value1 value2”
    content의 원소 중 값이 value1인 원소를 모두 value2로 변경합니다.

  3. “MERGE r1 c1 r2 c2”
    merged[r1][c1]의 값 (x1, y1)과 merged[r2][c2]의 값 (x2, y2)를 찾습니다. 그 후 merged의 원소 중 값이 (x2, y2)인 원소를 모두 (x1, y1)로 변경하고, 문제의 설명에 따라 content[x1][y1]의 값을 변경합니다.

  4. “UNMERGE r c”
    merged[r][c]의 값 (x, y)와 content[x][y]의 값 tmp를 찾습니다. merged[i][j]의 값이 (x, y)인 모든 i, j에 대해 merged[i][j]의 값을 (i, j)로, content[i][j]의 값을 “EMPTY”로 변경합니다. 마지막으로 content[r][c]의 값을 tmp로 변경합니다.

  5. “PRINT r c”
    merged[r][c]의 값 (x, y)를 찾아 content[x][y]의 값을 정답 배열에 추가합니다.

정답 코드

def solution(commands):
    answer = []
    merged = [[(i, j) for j in range(50)] for i in range(50)]
    board = [["EMPTY"] * 50 for _ in range(50)]
    for command in commands:
        command = command.split(' ')
        if command[0] == 'UPDATE':
            if len(command) == 4:
                r,c,value = int(command[1])-1,int(command[2])-1,command[3]
                x,y = merged[r][c]
                board[x][y] = value
            elif len(command) == 3:
                value1, value2 = command[1], command[2]
                for i in range(50):
                    for j in range(50):
                        if board[i][j] == value1:
                            board[i][j] = value2
        elif command[0] == 'MERGE':
            r1,c1,r2,c2 = int(command[1])-1, int(command[2])-1, int(command[3])-1, int(command[4])-1
            x1,y1 = merged[r1][c1]
            x2,y2 = merged[r2][c2]
            if board[x1][y1] == "EMPTY":
                board[x1][y1] = board[x2][y2]
            for i in range(50):
                for j in range(50):
                    if merged[i][j] == (x2,y2):
                        merged[i][j] = (x1,y1)
        elif command[0] == 'UNMERGE':
            r, c = int(command[1])-1,int(command[2])-1
            x, y = merged[r][c]
            tmp = board[x][y]
            for i in range(50):
                for j in range(50):
                    if merged[i][j] == (x,y):
                        merged[i][j] = (i,j)
                        board[i][j] = "EMPTY"
            board[r][c] = tmp
        elif command[0] == 'PRINT':
            r, c = int(command[1])-1, int(command[2])-1
            x, y = merged[r][c]
            answer.append(board[x][y])
    return answer

여담이지만 문제의 인덱스가 거의 1부터 시작하는 문제가 많다..(개발자 감수성 어디..)
일부러 헷갈리라고 그랬을수도..

profile
꾸준히 성장하는 개발자 지망생

0개의 댓글