[level 3] 표 병합 - 150366
성능 요약
메모리: 78.3 MB, 시간: 21.13 ms
구분
코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT
채점결과
정확성: 100.0
합계: 100.0 / 100.0
제출 일자
2025년 03월 19일 04:54:15
문제 설명
당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 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"명령어를 포함하고 있습니다.
입출력 예
| 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"명령어를 실행하면 아래와 같은 상태가 됩니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
문제 풀이
코드
import java.util.*;
class Solution {
static int[] p;
static String[] values;
static Map<Integer, List<Integer>> cellList = new HashMap<>();
public String[] solution(String[] commands) {
p = new int[2500];
values = new String[2500];
List<String> res = new ArrayList<>();
for(int i=0; i<2500; i++){
p[i] = i;
}
for(int i=0; i<2500; i++){
List<Integer> initialList = new ArrayList<>();
initialList.add(i);
cellList.put(i, initialList);
}
for(String command : commands){
String[] line = command.split(" ");
String type = line[0];
if(type.equals("UPDATE")){
// "UPDATE r c value"
if(line.length == 4){
int r = Integer.parseInt(line[1]) - 1;
int c = Integer.parseInt(line[2]) - 1;
String value = line[3];
int idx = r*50 + c;
values[find(idx)] = value;
}
// "UPDATE value1 value2"
else{
String value1 = line[1];
String value2 = line[2];
for(int i=0; i<2500; i++){
if(i==find(i) && value1.equals(values[i])){
values[i] = value2;
}
}
}
}
else if(type.equals("MERGE")){
int r1 = Integer.parseInt(line[1]) - 1;
int c1 = Integer.parseInt(line[2]) - 1;
int r2 = Integer.parseInt(line[3]) - 1;
int c2 = Integer.parseInt(line[4]) - 1;
int idx1 = r1 * 50 + c1;
int idx2 = r2 * 50 + c2;
int p1 = find(idx1);
int p2 = find(idx2);
// 이미 같음
if(p1 == p2) continue;
// 각 셀 빈거 체크
boolean is_p1_empty = false;
if(values[p1] == null) is_p1_empty=true;
boolean is_p2_empty = false;
if(values[p2] == null) is_p2_empty=true;
// 둘 다 비었으면 바로합치기
if(is_p1_empty && is_p2_empty) union(idx1, idx2);
// p2로 병합 (p1 비었고 p2값있음)
else if(is_p1_empty && !is_p2_empty) union(idx2, idx1);
// 둘다 값있으면 r1 c1쪽
else union(idx1, idx2);
}
else if(type.equals("UNMERGE")){
int r = Integer.parseInt(line[1]) - 1;
int c = Integer.parseInt(line[2]) - 1;
int idx = r * 50 + c;
String value = values[find(idx)];
// null로 초기화하고 r, c만 값할당
List<Integer> cells = new ArrayList<>(cellList.get(find(idx)));
for(int cellIdx : cells){
p[cellIdx] = cellIdx;
values[cellIdx] = null;
List<Integer> initialCell = new ArrayList<>();
initialCell.add(cellIdx);
cellList.put(cellIdx, initialCell);
}
values[idx] = value;
}
else if(type.equals("PRINT")){
int r = Integer.parseInt(line[1]) - 1;
int c = Integer.parseInt(line[2]) - 1;
int idx = r * 50 + c;
String value = values[find(idx)];
res.add(value == null ? "EMPTY" : value);
}
}
String[] ans = new String[res.size()];
for(int a=0; a<ans.length; a++){
ans[a] = res.get(a);
}
return ans;
}
static int find(int x){
if(p[x] != x) return p[x] = find(p[x]);
return p[x];
}
static void union(int x, int y){ // x를 부모로 합치기
int px = find(x);
int py = find(y);
if(px == py) return;
p[py] = px;
values[py] = null;
// 셀합치기
List<Integer> mergedCells = new ArrayList<>(cellList.get(px));
for(int i : cellList.get(py)){
mergedCells.add(i);
}
cellList.put(px, mergedCells);
cellList.put(py, mergedCells);
}
}
Studying Everyday