[Java] 2023 KAKAO BLIND RECRUITMENT 표 병합
- Gunn
- 2023년 12월 29일
- 6분 분량
최종 수정일: 2023년 12월 31일
Programmers에 공개된 2023 KAKAO BLIND RECRUITMENT (2023년 신입 공채 1차 온라인 코딩 테스트) 중에서 Lv.3로 설정되어 있는 표 병합 문제입니다.
1. 문제 및 조건
문제
당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 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"를 출력합니다.
입력
실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다.
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" 명령어를 포함하고 있습니다.
출력
"PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.
입출력 예시
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"] |
2. 설명
이 문제는 MERGE와 UNMERGE를 어떻게 처리하는 지가 큰 관건이라고 생각합니다. 일단 MERGE의 경우, 인접하지 않는 경우 두 셀만 영향을 받는다고 명시 되어 있기 때문에 떨어져 있는 셀도 MERGE가 가능합니다. 따라서, 셀이 인접하고 있는지는 딱히 검사를 하지 않아도 됩니다. MERGE를 했는지 표현하기 위해서 저는 Union Find(합집합 찾기) 알고리즘을 살짝 변형해서 사용했습니다.
Union Find 알고리즘을 사용할 경우, 왼쪽 그림과 같이 각 셀의 부모 좌표를 연결합니다. (3, 3)의 셀을 선택했을 때, MERGE되어 있는 모든 셀의 합집합은 (1, 1)셀이 되기 때문에 결과적으로 (1,1)셀이 선택됩니다. 이 연결을 트리 구조로 표현할 경우, 결국 최상단 노드(루트 노드)를 찾는 것이기 때문에 재귀 함수를 사용하는 구조가 됩니다.
오른쪽처럼 애초에 최상단 노드의 좌표를 저장한 이유는 UNMERGE를 실행할 때, UNMERGE를 실행한 횟수에 따라 MERGE한 순서대로 연결이 해제되어야 한다면 각 연결 좌표를 저장하는 게 필요하지만, UNMERGE 명령 한 번에 해당 좌표의 셀의 모든 연결을 끊기 때문에 모두 최상단 노드 좌표를 저장하고 좌표값이 UNMERGE를 실행할 때 해당 좌표가 가리키는 셀 좌표와 동일한 것을 모두 해제하는 편이 간결하게 코드를 구성할 수 있을 것 같아서 입니다.
3. 해결 방식
일단 50x50의 문자열을 저장할 2차원 배열 table과 해당 위치의 셀이 가리키는 셀을 지정할 50x50x2의 3차원 배열 merge를 선언합니다. merge배열은 초기값으로 자기 자신의 좌표를 저장합니다. 이후, 명령어 만큼 반복을 돌면서 실행할 함수를 분류시켜줍니다.
문제를 풀 때 주의할 점은 다음과 같습니다.
"제시되는 좌표값 - 1 = 인덱스" 입니다.
MERGE가 되어 있는 셀을 다시 MERGE할 경우, 연결되어 있는 모든 셀의 부모를 변경합니다.
UPDATE를 할 때 MERGE된 모든 셀을 변경합니다.
MERGE하는 최상위 셀의 좌표가 동일할 경우 무시합니다.
큰 틀은 동일하지만, 세부적으로는 두 가지 방식으로 생각해 볼 수 있을 것 같습니다.
MERGE를 실행할 때, 최상위 셀에 값을 저장하고 나머지는 비우는 방식
MERGE를 실행할 때, MERGE된 모든 셀에 같은 값을 저장하는 방식
1번 방식으로 해결할 경우는 다음과 같이 해결합니다.
MERGE를 실행할 때 셀에 규칙에 맞는 값을 변수에 따로 저장한 후, MERGE를 진행하면서 모든 셀의 값을 비웁니다. 이후, 최상위 셀에만 값을 저장합니다.
UNMERGE를 실행할 때는 최상위 셀의 값을 변수에 따로 저장한 후, 최상위 노드만 비웁니다. 이후, 최상위 노드를 가리키고 있는 모든 셀을 자신을 가라키도록 변경하고 지정된 좌표에 값을 다시 넣어줍니다.
UPDATE시에는 좌표가 가리키고 있는 최상위 셀의 값만 변경합니다.
PRINT할 때는 셀 좌표의 최상위 셀 좌표에 들어 있는 값을 출력합니다.
2번 방식으로 해결할 경우는 다음과 같이 해결합니다.
MERGE를 실행할 때 규칙에 맞는 값을 변수에 따로 저장한 후, MERGE를 진행하면서 모든 셀에 값을 저장합니다.
UNMERGE를 실행할 때는 해당 셀의 값을 변수에 따로 저장한 후, 최상위 셀을 가리키고 있는 모든 셀을 자신을 가리키도록 변경하면서 값을 모두 비웁니다. 이후, 지정된 좌표에 값을 다시 넣어줍니다.
UPDATE시에는 해당 좌표가 가리키고 있는 셀의 좌표를 가지고 있는 모든 셀을 변경합니다.
PRINT할 때는 해당 셀의 좌표값을 출력합니다.
4. 코드
1번 방식으로 해결 할 경우
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
public class Solution5 {
private static final int SIZE = 50;
private String[][] table = new String[SIZE][SIZE];
private int[][][] merge = new int[SIZE][SIZE][2];
public static void main(String[] args){
Solution5 solution5 = new Solution5();
String[] commands = {
"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"
};
String[] result = solution5.solution(commands);
System.out.print("result = ");
for(String r : result){
System.out.print(r+" ");
}
System.out.println();
}
public String[] solution(String[] commands) {
List<String> printList = new ArrayList<>();
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
merge[i][j][0] = i;
merge[i][j][1] = j;
}
}
for(String command : commands){
String[] commandSplit = command.split(" ");
if(Objects.equals(commandSplit[0], "UPDATE")){
if(commandSplit.length == 3){
update(commandSplit[1], commandSplit[2]);
}else if(commandSplit.length == 4){
update(Integer.valueOf(commandSplit[1])-1, Integer.valueOf(commandSplit[2])-1, commandSplit[3]);
}
}else if(Objects.equals(commandSplit[0], "MERGE")){
merge(Integer.valueOf(commandSplit[1])-1, Integer.valueOf(commandSplit[2])-1, Integer.valueOf(commandSplit[3])-1, Integer.valueOf(commandSplit[4])-1);
}else if(Objects.equals(commandSplit[0], "UNMERGE")){
unmerge(Integer.valueOf(commandSplit[1])-1, Integer.valueOf(commandSplit[2])-1);
}else if(Objects.equals(commandSplit[0], "PRINT")){
printList.add(print(Integer.valueOf(commandSplit[1])-1, Integer.valueOf(commandSplit[2])-1));
}
}
String[] answer = printList.toArray(new String[printList.size()]);
return answer;
}
private void update(int r, int c, String value){
int[] root = merge[r][c];
table[root[0]][root[1]] = value;
}
private void update(String value1, String value2){
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
if(Objects.equals(table[i][j], value1)){
update(i, j, value2);
}
}
}
}
private void merge(int r1, int c1, int r2, int c2){
int[] root1 = merge[r1][c1].clone();
int[] root2 = merge[r2][c2].clone();
if(root1[0] == root2[0] && root1[1] == root2[1]) return;
String value = Objects.equals(table[root1[0]][root1[1]], null) ? table[root2[0]][root2[1]] : table[root1[0]][root1[1]];
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
if(merge[i][j][0] == root2[0] && merge[i][j][1] == root2[1]){
merge[i][j][0] = root1[0];
merge[i][j][1] = root1[1];
table[i][j] = null;
}
}
}
update(root1[0], root1[1], value);
}
private void unmerge(int r, int c){
int[] root = merge[r][c].clone();
String value = table[root[0]][root[1]];
table[root[0]][root[1]] = null;
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
if(merge[i][j][0] == root[0] && merge[i][j][1] == root[1]){
merge[i][j][0] = i;
merge[i][j][1] = j;
}
}
}
table[r][c] = value;
}
private String print(int r, int c){
int[] root = merge[r][c];
String result = "EMPTY";
if(!Objects.equals(table[root[0]][root[1]], null)){
result = table[root[0]][root[1]];
}
return result;
}
}2번 방식으로 해결 할 경우
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
public class Solution5 {
private static final int SIZE = 50;
private String[][] table = new String[SIZE][SIZE];
private int[][][] merge = new int[SIZE][SIZE][2];
public static void main(String[] args){
Solution5 solution5 = new Solution5();
String[] commands = {
"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"
};
String[] result = solution5.solution(commands);
System.out.print("result = ");
for(String r : result){
System.out.print(r+" ");
}
System.out.println();
}
public String[] solution(String[] commands) {
List<String> printList = new ArrayList<>();
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
merge[i][j][0] = i;
merge[i][j][1] = j;
}
}
for(String command : commands){
String[] commandSplit = command.split(" ");
if(Objects.equals(commandSplit[0], "UPDATE")){
if(commandSplit.length == 3){
update(commandSplit[1], commandSplit[2]);
}else if(commandSplit.length == 4){
update(Integer.valueOf(commandSplit[1])-1, Integer.valueOf(commandSplit[2])-1, commandSplit[3]);
}
}else if(Objects.equals(commandSplit[0], "MERGE")){
merge(Integer.valueOf(commandSplit[1])-1, Integer.valueOf(commandSplit[2])-1, Integer.valueOf(commandSplit[3])-1, Integer.valueOf(commandSplit[4])-1);
}else if(Objects.equals(commandSplit[0], "UNMERGE")){
unmerge(Integer.valueOf(commandSplit[1])-1, Integer.valueOf(commandSplit[2])-1);
}else if(Objects.equals(commandSplit[0], "PRINT")){
printList.add(print(Integer.valueOf(commandSplit[1])-1, Integer.valueOf(commandSplit[2])-1));
}
}
String[] answer = printList.toArray(new String[printList.size()]);
return answer;
}
private void update(int r, int c, String value){
int[] root = merge[r][c];
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
if(merge[i][j][0] == root[0] && merge[i][j][1] == root[1]){
table[i][j] = value;
}
}
}
}
private void update(String value1, String value2){
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
if(Objects.equals(table[i][j], value1)){
update(i, j, value2);
}
}
}
}
private void merge(int r1, int c1, int r2, int c2){
int[] root1 = merge[r1][c1].clone();
int[] root2 = merge[r2][c2].clone();
if(root1[0] == root2[0] && root1[1] == root2[1]) return;
String value = Objects.equals(table[root1[0]][root1[1]], null) ? table[root2[0]][root2[1]] : table[root1[0]][root1[1]];
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
if(merge[i][j][0] == root2[0] && merge[i][j][1] == root2[1]){
merge[i][j][0] = root1[0];
merge[i][j][1] = root1[1];
}
}
}
update(root1[0], root1[1], value);
}
private void unmerge(int r, int c){
int[] root = merge[r][c].clone();
String value = table[root[0]][root[1]];
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
if(merge[i][j][0] == root[0] && merge[i][j][1] == root[1]){
merge[i][j][0] = i;
merge[i][j][1] = j;
table[i][j] = null;
}
}
}
table[r][c] = value;
}
private String print(int r, int c){
String result = "EMPTY";
if(!Objects.equals(table[r][c], null)){
result = table[r][c];
}
return result;
}
}
Comments