문제
https://school.programmers.co.kr/learn/courses/30/lessons/150366
문제 설명
당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.
위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.
-
"UPDATE r c value"- (
r,c) 위치의 셀을 선택합니다. - 선택한 셀의 값을
value로 바꿉니다.
- (
-
"UPDATE value1 value2"value1을 값으로 가지고 있는 모든 셀을 선택합니다.- 선택한 셀의 값을
value2로 바꿉니다.
-
"MERGE r1 c1 r2 c2"
- (
r1,c1) 위치의 셀과 (r2,c2) 위치의 셀을 선택하여 병합합니다. - 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
- 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (
r1,c1) 위치의 셀과 (r2,c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다. - 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
- 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (
r1,c1) 위치의 셀 값을 가지게 됩니다. - 이후 (
r1,c1) 와 (r2,c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
- (
-
"UNMERGE r c"- (
r,c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다. - 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
- 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (
r,c) 위치의 셀이 그 값을 가지게 됩니다.
- (
-
"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가지 형태 중 하나입니다."UPDATE r c value"r,c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
"UPDATE value1 value2"value1은 선택할 셀의 값,value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
"MERGE r1 c1 r2 c2"
r1,c1,r2,c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
"UNMERGE r c"r,c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
"PRINT r c"
r,c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
commands는 1개 이상의"PRINT r c"명령어를 포함하고 있습니다.
접근 방식
처음 이 문제를 시험날 봤을 때 쉬워보였다.
단순 구현 문제인것 같았으며, 단순하기 삽입, 출력만 하는 듯한 문제였기 때문이다.
그런데 MERGE의 존재 하나로 너무나도 어렵게 느껴졌던 문제였다.
그런데 카카오 테크 블로그의 해설은 정말 단순 구현 이었다.
문제의 핵심 해결 포인트는
- 각 표의 인덱스를 관리하는
merge자료구조를 하나 둔다. - 각 표의 값을 관리하는
content자료구조를 하나 둔다.
이게 끝이다..
그냥 각 표의 값에 접근할 때는 인덱스를 관리하는 merge를 거쳐서 접근하도록만 설계하면 끝나는 문제였다...
이 문제의 해결 방식은 카카오 테크 블로그에 설명을 그대로 따라가면 풀리는 문제이므로, 해당 블로그를 참고하면 된다.
-
“UPDATE r c value”
merged[r][c]의 값 (x, y)를 찾아 content[x][y]의 값을 value로 변경합니다. -
“UPDATE value1 value2”
content의 원소 중 값이 value1인 원소를 모두 value2로 변경합니다. -
“MERGE r1 c1 r2 c2”
merged[r1][c1]의 값 (x1, y1)과 merged[r2][c2]의 값 (x2, y2)를 찾습니다. 그 후 merged의 원소 중 값이 (x2, y2)인 원소를 모두 (x1, y1)로 변경하고, 문제의 설명에 따라 content[x1][y1]의 값을 변경합니다. -
“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로 변경합니다. -
“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부터 시작하는 문제가 많다..(개발자 감수성 어디..)
일부러 헷갈리라고 그랬을수도..
