프로그래머스 표 병합 (2023 KAKAO BLIND RECRUITMENT)

문제 설명

당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 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" 입력

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

아래는 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 함수를 완성해주세요.

제한 사항

• 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" 명령어를 포함하고 있습니다.

입출력 예

commands	result
["UPDATE 1 1 menu", "UPDATE 1 2 category", "UPDATE 2 1 bibimbap", "UPDATE 2 2 korean", "UPDATE 2 3 rice", "UPDATE 3 1 ramyeon", "UPDATE 3 2 korean", "UPDATE 3 3 noodle", "UPDATE 3 4 instant", "UPDATE 4 1 pasta", "UPDATE 4 2 italian", "UPDATE 4 3 noodle", "MERGE 1 2 1 3", "MERGE 1 3 1 4", "UPDATE korean hansik", "UPDATE 1 3 group", "UNMERGE 1 4", "PRINT 1 3", "PRINT 1 4"]	["EMPTY", "group"]
["UPDATE 1 1 a", "UPDATE 1 2 b", "UPDATE 2 1 c", "UPDATE 2 2 d", "MERGE 1 1 1 2", "MERGE 2 2 2 1", "MERGE 2 1 1 1", "PRINT 1 1", "UNMERGE 2 2", "PRINT 1 1"]	["d", "EMPTY"]

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다. (1,3) 위치의 셀은 비어있고 (1,4) 위치의 셀 값은 "group"입니다. 따라서 ["EMPTY", "group"]을 return 해야 합니다.

입출력 예 #2

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

• "MERGE 1 1 1 2" 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "MERGE 2 2 2 1" 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "MERGE 2 1 1 1" 명령어를 실행하면 아래와 같은 상태가 됩니다.

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

풀이

• 참조에 참조에 참조에... 배열에 배열에 배열에 ㅋㅋㅋ
  • 시간만 낭비한 것 같다.
    • 더 단순한 방법을 해보자
• 문제를 보다보니까 merge가 병신같은 조건이 달려있네...
  • 난 r1 c1 r2 c2 범위 내 모든 셀의 참조를 바꿔야한다고 생각했는데,
    • 지금 다시 보니까 그냥 2셀의 참조만 바꿔주는 것...
• 데이터 저장 메커니즘과 접근을 한번에 끝낼 수 있도록 해보자
  • 저장공간
    • 시트 정보
      • sheet(51x51)라는 이름의 배열을 만들고,
        • 값 참조 : test1 = [1,1]
        • 합병셀 참조 : test2 = [1,2,3,4]
    • 값 정보
      • values = {}로 만들고, 다음과 같이 저장
        • 값셀 : values[(1,1)] = "babo"
        • 합병셀 : values[(1,2,3,4)] = "merged"
  • 구현
    • 명령을 커맨드 별로 분리하는 함수를 하나 만들고,
    • 각 함수에서 개별 커맨드로 분기
    • sheet와 value에서 값을 꺼낼 때는 데이터의 길이로 어떤 종류인지 판별한다.
      • 값 셀 : len(test1)
      • 합병 셀 : len(test2)
  • 명령어별 구현
    • UPDATE r c value
      • 해당 셀에 참조가 있으면 values에서 값을 변경함
      • 해당 셀에 참조가 없으면 참조를 만들고, values에 값을 추가함
    • UPDATE value1 value2
      • values 테이블 전수 검사해서 value1이 있으면 value2로 변경
      • 모든 셀의 값이 바뀌는 것이므로 끝까지 for문 돌리면 됨
        • for k,v in list(values.items())로 
    • MERGE r1 c1 r2 c2
      • sheet의 두 셀 (r1, c1), (r2, c2)의 참조를 동일한 걸로 변경
      • r1 c1 = r2 c2 면 스킵
      • 해당 범위 내에 값이 있는 셀이 있는지 체크해서 값을 r1 c1로. 두셀 모두 값이 있으면 r1 c1 기준
    • UNMERGE r c
      • 해당 위치에 있는 셀이 병합 셀이면 sheet for문 돌려서 참조해제하고,
      • values[r c]에 value[r1 c1 r2 c2] 값을 넣기
    • 어라? 된다!?

• 이전에 있던 값들 지우지 않아도 되는 듯? ㅇㅋ 가즈아!

def solution(commands):
    answer = []
    sheet = [['']*51 for i in range(51)]
    values = {'':"EMPTY"}

    for cmd in commands:
        cmd = cmd.split(sep=' ')
        if cmd[0] == "UPDATE":
            if len(cmd) == 3: # 리네임
                source = cmd[1]
                target = cmd[2]
                for k,v in list(values.items()):
                    if v == source:
                        values[k] = target
            else: # 업데이트
                r = int(cmd[1])
                c = int(cmd[2])
                v = cmd[3]
                source = sheet[r][c]
                if source == '': # 빈셀
                    sheet[r][c] = (r,c)
                    values[(r,c)] = v
                else:
                    values[source] = v
        elif cmd[0] == "PRINT": # print("프린트")
            r = int(cmd[1])
            c = int(cmd[2])
            source = sheet[r][c]
            answer.append(values[source])
        elif cmd[0] == "MERGE":
            r1 = int(cmd[1])
            c1 = int(cmd[2])
            r2 = int(cmd[3])
            c2 = int(cmd[4])
            source1 = sheet[r1][c1]
            source2 = sheet[r2][c2]
            if source1 == '' and source2 == '': # 빈셀, 빈셀
                sheet[r1][c1] = (r1,c1)
                sheet[r2][c2] = (r2,c2)
            elif source1 == '': # 빈셀 vs 값셀
                sheet[r1][c1] = sheet[r2][c2]
            elif source2 == '': # 값셀 vs 빈셀
                sheet[r2][c2] = sheet[r1][c1]
            else: # 값셀/병합셀 vs 갑셀/병합셀
                for i in range(51):
                    for j in range(51):
                        if sheet[i][j] == source2:
                            sheet[i][j] = source1
        elif cmd[0] == "UNMERGE": # print("언머지")
            r = int(cmd[1])
            c = int(cmd[2])
            source = sheet[r][c]
            v = values[source]
            for i in range(51):
                for j in range(51):
                    if sheet[i][j] == source:
                        sheet[i][j] = ''
            sheet[r][c] = (r,c)
            values[(r,c)] = v
    
    return answer

• 잉? 왠 런타임 에러...

• 머지랑 언머지, 값 넣기. 다 확인했는데... 힝 왜 안돼
• 테스트케이스 6번 11번이 실패한다.

• 그냥 첨부터 값을 다 넣어 놓고 시작해도 되는구나... ㅡ.ㅡ;

def solution(commands):
    answer = []
    sheet = [[(i,j) for j in range(51)] for i in range(51)]
    values = {(i,j):'' for j in range(51) for i in range(51)}

    for cmd in commands:
        cmd = cmd.split(sep=' ')
        if cmd[0] == "UPDATE" and len(cmd) == 3: # 리네임
            source = cmd[1]
            target = cmd[2]
            for k,v in values.items():
                if v == source:
                    values[k] = target
        if cmd[0] == "UPDATE" and len(cmd) == 4: # 업데이트
            r = int(cmd[1])
            c = int(cmd[2])
            v = cmd[3]
            source = sheet[r][c]
            values[source] = v
        elif cmd[0] == "PRINT": # print("프린트")
            r = int(cmd[1])
            c = int(cmd[2])
            source = sheet[r][c]
            if values[source] != '':
                answer.append(values[source])
            else:
                answer.append("EMPTY")
        elif cmd[0] == "MERGE":
            r1 = int(cmd[1])
            c1 = int(cmd[2])
            r2 = int(cmd[3])
            c2 = int(cmd[4])
            source1 = sheet[r1][c1]
            source2 = sheet[r2][c2]
            if source1 == source2:
                continue
            if values[source1] != '': # 빈셀 vs 값셀
                v_source1 = values[source1]
                for i in range(51):
                    for j in range(51):
                        if sheet[i][j] == source2:
                            sheet[i][j] = source1
            else:
                v_source2 = values[source2]
                for i in range(51):
                    for j in range(51):
                        if sheet[i][j] == source1:
                            sheet[i][j] = source2
        elif cmd[0] == "UNMERGE": # print("언머지")
            r = int(cmd[1])
            c = int(cmd[2])
            source = sheet[r][c]
            v = values[source]
            for i in range(51):
                for j in range(51):
                    if sheet[i][j] == source:
                        sheet[i][j] = (i,j)
                        values[(i,j)] = ''
            values[(r,c)] = v
    
    return answer

정확성  테스트
테스트 1 〉	통과 (1.54ms, 10.7MB)
테스트 2 〉	통과 (1.42ms, 10.7MB)
테스트 3 〉	통과 (0.76ms, 10.7MB)
테스트 4 〉	통과 (0.74ms, 10.6MB)
테스트 5 〉	통과 (1.16ms, 10.7MB)
테스트 6 〉	통과 (1.75ms, 10.8MB)
테스트 7 〉	통과 (1.29ms, 10.8MB)
테스트 8 〉	통과 (1.55ms, 10.6MB)
테스트 9 〉	통과 (3.45ms, 10.8MB)
테스트 10 〉	통과 (4.13ms, 10.6MB)
테스트 11 〉	통과 (6.84ms, 10.6MB)
테스트 12 〉	통과 (15.11ms, 10.9MB)
테스트 13 〉	통과 (46.35ms, 10.8MB)
테스트 14 〉	통과 (43.27ms, 10.9MB)
테스트 15 〉	통과 (75.67ms, 10.8MB)
테스트 16 〉	통과 (64.56ms, 10.9MB)
테스트 17 〉	통과 (73.67ms, 10.9MB)
테스트 18 〉	통과 (67.36ms, 10.8MB)
테스트 19 〉	통과 (70.56ms, 10.9MB)
테스트 20 〉	통과 (153.35ms, 10.8MB)
테스트 21 〉	통과 (174.97ms, 11MB)
테스트 22 〉	통과 (80.95ms, 11MB)

• 고수의 풀이를 보면
  • 튜플이 아닌 값으로 하는 방식도 있고

def solution(commands):
    answer = []
    sheet = [[51 * i + j for j in range(51)] for i in range(51)]
    values = {i : '' for i in range(51*51)}

    for cmd in commands:
        cmd = list(cmd.split(sep=' '))
        if cmd[0] == "UPDATE" and len(cmd) == 3: # 리네임
            source = cmd[1]
            target = cmd[2]
            for k,v in values.items():
                if v == source:
                    values[k] = target
        elif cmd[0] == "UPDATE" and len(cmd) == 4:  # 업데이트
            r = int(cmd[1])
            c = int(cmd[2])
            v = cmd[3]
            source = sheet[r][c]
            values[source] = v
        elif cmd[0] == "PRINT": # print("프린트")
            r = int(cmd[1])
            c = int(cmd[2])
            source = sheet[r][c]
            if values[source] != '':
                answer.append(values[source])
            else:
                answer.append("EMPTY")
        elif cmd[0] == "MERGE":
            r1 = int(cmd[1])
            c1 = int(cmd[2])
            r2 = int(cmd[3])
            c2 = int(cmd[4])
            source1 = sheet[r1][c1]
            source2 = sheet[r2][c2]
            if source1 == source2:
                continue
            if values[source1] != '':
                for i in range(51):
                    for j in range(51):
                        if sheet[i][j] == source2:
                            sheet[i][j] = source1
            else:
                for i in range(51):
                    for j in range(51):
                        if sheet[i][j] == source1:
                            sheet[i][j] = source2
        elif cmd[0] == "UNMERGE": # print("언머지")
            r = int(cmd[1])
            c = int(cmd[2])
            source = sheet[r][c]
            v = values[source]
            for i in range(51):
                for j in range(51):
                    if sheet[i][j] == source:
                        sheet[i][j] = 51 * i + j
                        values[sheet[i][j]] = ''
            values[sheet[r][c]] = v
        
        # print(cmd)
        # for i in range(11):
        #     for j in range(11):
        #         print(sheet[i][j],end="|")
        #     print("")
        # print("="*10)
        # print(values)
        # print("="*10)
    return answer

• 그냥 2차원 배열에 내용과 참조를 같이 넣는 방식도 되는구나.

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":
            if len(li) == 4:
                for r,c in board[int(li[1])][int(li[2])][1]:
                    board[r][c][0] = li[3]
            else:
                for y in range(1,51):
                    for x in range(1,51):
                        if board[y][x][0] == li[1]:
                            board[y][x][0] = li[2]

        if li[0] == "MERGE":
            r1,c1 = int(li[1]),int(li[2])
            r2,c2 = int(li[3]),int(li[4])
            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

            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":

            for r,c in board[int(li[1])][int(li[2])][1]:
                if r == int(li[1]) and c == int(li[2]):
                    pass
                else:
                    board[r][c][1] = [(r,c)]
                    board[r][c][0] = ""
            board[int(li[1])][int(li[2])][1] = [(int(li[1]),int(li[2]))]

        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

• 근데 딱히 자료형이나 알고리즘 보다는 그냥 구현 문제 같다.
• 검색해보니까 유니온파인드 문제라고 나오던데...
  • (사실은 뭔지 몰라... 소곤소곤)
  • 나중에 공부해보자...