2023 KAKAO BLIND RECRUITMENT 1차 코딩 테스트 문제이다.
실제 작년 코테에 응시하여 문제를 풀어봤는데 그때는 어떻게 접근해야될지 몰랐다.
문제풀이에 2시간 정도 걸렸지만 그래도 풀었다는 사실에 뿌듯하다
제출코드
파이썬
def solution(commands):
table = [[0] * 51 for _ in range(51)]
uniqueKey = 0
for i in range(1, 51):
for j in range(1, 51):
table[i][j] = ["", uniqueKey]
uniqueKey +=1
def updateA(i, j, word):
nonlocal table
key = table[i][j][1]
for i in range(1, 51):
for j in range(1, 51):
if table[i][j][1] == key:
table[i][j][0] = word
def updateB(a, b):
nonlocal table
for i in range(1, 51):
for j in range(1, 51):
if table[i][j][0] == a:
table[i][j][0] = b
def merge(r1, c1, r2, c2):
nonlocal table, uniqueKey
keyA, keyB = table[r1][c1][1], table[r2][c2][1]
if keyA == keyB:
return
word = table[r1][c1][0]
if (table[r1][c1][0] == "" and table[r2][c2][0] != "") :
word = table[r2][c2][0]
for i in range(1, 51):
for j in range(1, 51):
if (table[i][j][1] == keyA or table[i][j][1] == keyB):
table[i][j] = [word, uniqueKey]
uniqueKey += 1
def unmerge(r, c):
nonlocal uniqueKey, table
word = table[r][c][0]
key = table[r][c][1]
for i in range(1, 51):
for j in range(1, 51):
if table[i][j][1] == key:
table[i][j] = ["", uniqueKey]
uniqueKey += 1
table[r][c][0] = word
ans = []
for s in commands:
com = s.split()
if com[0] == "UPDATE":
if len(com) == 4:
i, j, word = com[1], com[2], com[3]
updateA(int(i), int(j), word)
else:
a, b = com[1], com[2]
updateB(a, b)
elif com[0] == "MERGE":
r1, c1, r2, c2 = map(int, com[1:])
merge(r1, c1, r2, c2)
elif com[0] == "UNMERGE":
r, c = map(int, com[1:])
unmerge(r, c)
else:
r, c = map(int, com[1:])
w = table[r][c][0]
if w == "":
w = "EMPTY"
ans.append(w)
return ans
자바
import java.util.*;
class Solution {
static Node[][] table = new Node[51][51];
static int uniqueKey = 0;
public ArrayList solution(String[] commands) {
ArrayList answer = new ArrayList();
for (int i = 1; i < 51; i++) {
for (int j = 1; j < 51; j++) {
Node node = new Node("", uniqueKey);
table[i][j] = node;
uniqueKey += 1;
}
}
for (String com : commands) {
String[] arrCom = com.split(" ");
if (arrCom[0].equals("UPDATE")) {
if (arrCom.length == 4) {
int r = Integer.parseInt(arrCom[1]);
int c = Integer.parseInt(arrCom[2]);
updateA(r, c, arrCom[3]);
} else {
updateB(arrCom[1], arrCom[2]);
}
} else if (arrCom[0].equals("MERGE")) {
int r1 = Integer.parseInt(arrCom[1]);
int c1 = Integer.parseInt(arrCom[2]);
int r2 = Integer.parseInt(arrCom[3]);
int c2 = Integer.parseInt(arrCom[4]);
merge(r1, c1, r2, c2);
} else if (arrCom[0].equals("UNMERGE")) {
int r = Integer.parseInt(arrCom[1]);
int c = Integer.parseInt(arrCom[2]);
unmerge(r, c);
} else {
int r = Integer.parseInt(arrCom[1]);
int c = Integer.parseInt(arrCom[2]);
String word = table[r][c].word;
if (word.equals("")) {
word = "EMPTY";
}
answer.add(word);
}
}
return answer;
}
public void updateA(int si, int sj, String word) {
int key = table[si][sj].key;
for (int i = 1; i < 51; i++) {
for (int j = 1; j < 51; j++) {
if (table[i][j].key == key) {
table[i][j].word = word;
}
}
}
}
public void updateB(String a, String b) {
for (int i = 1; i < 51; i++) {
for (int j = 1; j < 51; j++) {
if (table[i][j].word.equals(a)) {
table[i][j].word = b;
}
}
}
}
public void merge(int r1, int c1, int r2, int c2) {
int keyA = table[r1][c1].key;
int keyB = table[r2][c2].key;
String word = table[r1][c1].word;
if (word.equals("") && !table[r2][c2].word.equals("")) {
word = table[r2][c2].word;
}
for (int i = 1; i < 51; i++) {
for (int j = 1; j < 51; j++) {
if ((table[i][j].key == keyA) || (table[i][j].key == keyB)) {
table[i][j].word = word;
table[i][j].key = uniqueKey;
}
}
}
uniqueKey += 1;
}
public void unmerge(int r, int c) {
int key = table[r][c].key;
String word = table[r][c].word;
for (int i = 1; i < 51; i++) {
for (int j = 1; j < 51; j++) {
if (table[i][j].key == key) {
table[i][j].key = uniqueKey;
table[i][j].word = "";
uniqueKey += 1;
}
}
}
table[r][c].word = word;
}
}
class Node {
int key;
String word;
public Node(String word, int key) {
this.key = key;
this.word = word;
}
}접근방법
조건에 표의 크기가 50x50 으로 고정되어 있었기 때문에 50x50 의 2차원 배열(table)을 만들고 시작했다.
내 생각에 이 문제는 표를 병합하고 병합을 해제했을때 결과를 구분할 방법을 찾는게 핵심이라고 생각했고 나는 uniqueKey라는 변수를 만들어 해결했다.
table에는 표의 문자열값과 uniqueKey 정보가 들어가게 되는데 같은 uniqueKey값을 가진다면 그 표들은 병합된 상태라는 의미를 가진다.
uniqueKey값을 체크해야 되기 때문에 모든 메서드에서 완전탐색을 시도해야 되지만, 명령어 개수 1000개, table 크기 50x50으로 무리없다고 판단했다.
뚝딱뚝딱