Programmersに公開された2023 KAKAO BLIND RECRUITMENT（2023年新入債務第一次オンラインコーディングテスト）の中でLv.3に設定されている表のマージです。
1. 問題と条件
問題
貴方は表の編集プログラムを作成しています。
表の大きさは50x50に固定されていて、初期に全てのセルは空いています。
各セルは文字列の値を持つことができて、他のセルとマージできます。
上からr番目、左からc番目の位置を（r、c）だと表現する時、次の命令語たちに対した機能を作成しようとします。
"UPDATE r c value"
（r、c）位置のセルを選択します。
選択したセルの値をvalueに変えます。
"UPDATE value1 value2"
value1を値で持っている全てのセルを選択します。
選択したセルの値をvalue２に変えます。
"MERGE r1 c1 r2 c2"
（r１、c１）位置のセルと（r２、c２）位置のセルを選択してマージします。選択した二つのセルが同じセルである場合は無視します。
選択した二つのセルは互いに隣接していない可能性があります。この場合（r１、c１）位置のセルと（r２、c２）位置のセルだけ影響を受けて、その間に位置しているセルは影響を受けません。
二つのセルの中で一つのセルが値を持っている場合マージされたセルはその値を持ちます。
二つのセルが全て値を持っている場合マージされたセルは（r１、c１）位置のセルの値を持ちます。
その後（r１、c１）と（r２、c２）の中でどの位置を選択してもマージされたセルに接近します。
"UNMERGE r c"
（r、c）位置のセルを選択してそのセルの全てのマージを解除します。
選択したセルが含まれていた全てのセルはプログラム実行初期状態に戻ります。
マージを解除する前のセルが値を持っている場合（r、c）位置のセルはその値を持ちます。
"PRINT r c"
（r、c）位置のセルを選択してセルの値を出力します。
選択したセルが空いてる場合「EMPTY」を出力します。
入力
実行する命令語たちが入っている１次元文字列配列commandsがパラメータで与えられます。
1 ≤ commandsの長さ ≤ 1,000
commandsの各元素は下記の5つの形式の1つです。
"UPDATE r c value"
r、cは選択するセルの位置を表して、1〜50の間の定数です。
valueはセルに入力する内容を表して、アルファベット小文字と数字で構成された長さ1〜10の間である文字列です。
"UPDATE value1 value2"
value1は選択するセルの値、value2はセルに入力する内容を表して、アルファベット小文字と数字で構成された長さ1〜10の間の文字列です。
"MERGE r1 c1 r2 c2"
r１、c１、r２、c２は選択するセルの位置を表して、1〜50の間の定数です。
"UNMERGE r c"
r、cは選択するセルの位置を表して、1〜50の間の定数です。
"PRINT r c"
r、cは選択するセルの位置を表して、1〜50の間の定数です。
commandsは一つ以上の「PRINT r c」命令語を含めています。
出力
「PRINT r c」命令語に対した実行結果を順番で１次元文字列配列に入れて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の場合、隣接していない場合、2つのセルのみが影響を受けると明示されているので、離れているセルもMERGEが可能です。それで、セルが隣接しているのかは別に検査しなくてもいいです。MERGEをしたのかを表現する為に私はUnion Find（和集合探し）アルゴリズムを少し変更して使いました。
Union Findアルゴリズムを使う場合、左の絵みたいに各セルの親座標を繋げます。（3、3）のセルを選択した時、MERGEされている全てのセルの和集合は（1、1）になるため、結果的に（1、1）が選択されます。この繋がりをツリー構造で表現する場合、結局は最上段ノード（ルートノード）を探すことであるため再帰関数を使用する構造になります。
右の絵みたいに最上段ノードの座標を保存する理由はUNMERGEを実行する時、UNMERGEを実行した回数によってMERGEした順番で繋がりが解除する必要があれば各繋がりの座標を保存するべきだけど、UNMERGEの命令一回で座標にあるセルの全ての繋がりを切るため、全て最上段ノード座標を保存して座標値をUNMERGEを実行する時の座標が指すセルの座標と同一なものを全て解除する方が簡潔にコードを作れそうだからです。
3. 解決方法
50ｘ50の文字列を保存する2次元配列tableとその位置のセルが指しているセルを指定する50ｘ50ｘ2の3次元定数配列mergeを宣言します。merge配列は初期値で自分自身の座標を保存します。その後、命令語の分繰り返しながら実行する関数を分類します。
問題を解く時の注意点は下記のようです。
「提示される座標値ー１＝インデックス」です。
MERGEされているセルをまたMERGEする場合、繋がっている全てのセルの親を変更します。
UPDATEをする時、MERGEされている全てのセルを変更します。
MERGEする最上位セルの座標は同一な場合は無職します。
大きな枠は同じですが、詳細には2つの方法で考えることができそうです。
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;
}
}
Comentários