https://school.programmers.co.kr/learn/courses/30/lessons/150366#
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드설명
구현 혹은 유니온 파인드를 활용하는 문제입니다.
저 같은경우 일반 구현으로 구현했습니다.
구현을 통해 진행할경우 시간초과를 우려할 수 있지만,
N의 범위가 50 x 50 이므로 통과할 수 있습니다.
유니온 파인드를 활용하여 해결할경우, 시간복잡도를 줄여서 더 빠르게 해결할 수 있을 것 입니다.
이 문제에서 가장 중요한점은, 문제를 완벽히 이해하는것입니다.
예시를 들면, 이 문제에서 가장 쉽게 놓칠 수 있는 부분은
1. "MERGE" 과정에서 비어있는 셀들도 병합이 되도록 처리한다.
2. "MERGE r c " 과정에서 r 의 값이 비어있다면 c 값으로 r이 변환된다.
등등의 점들이 있습니다.
제 코드에 기반하여 문제 로직에 대해 정리해보겠습니다.
1. Node 객체 생성
class Node{
int mergedX; //병합코드의 ParentX
int mergedY; //병합코드의 ParentY
String value; //값 ( 비어있을시 "" )
public Node(int mergedX, int mergedY, String value){
this.mergedX = mergedX;
this.mergedY = mergedY;
this.value = value;
}
}- mergedX, mergedY 는 병합셀의 부모셀을 의미합니다. 첫 초기화 시 본인의 X, Y 좌표를 가집니다.
- 만약 merged 1 2 1 3 이 들어왔다고 가정했을때, 첫번쨰 좌표의 mergedX, mergedY = (1, 2) 두번째 좌표의 mergedX, mergedY = (1, 2) 로 1,3 의 좌표값이 1, 2 로 변경됩니다.
- merged 1 2 1 3 일때 무조건 r1 c1 이 병합의 부모가 되도록 설정합니다. ( r2 c2의 mergedX,Y가 r1.mergedX, c1.mergedY의 값이 된다는 의미입니다.)
- 추가적인 설명은 아래에서 더 나옵니다.
2. update r c value
//update r c value
if(command.equals("UPDATE") && splitCommands.length == 4){
int r = Integer.parseInt(splitCommands[1]);
int c = Integer.parseInt(splitCommands[2]);
String value = splitCommands[3];
System.out.print(splitCommands[1]+" "+splitCommands[2]+" "+splitCommands[3]+" ");
graph[r][c].value = value;
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].mergedX == graph[r][c].mergedX && graph[k][j].mergedY == graph[r][c].mergedY){ //r c와 병합된 모든것들을 수정하기 위하여 입니다.
graph[k][j].value = graph[r][c].value;
}
}
}
}- "UPDATE 1 1 menu"가 들어왔을때 r c의 셀을 menu 로 변경시킵니다.
- 단순히 해당 값만 변경되는것이 아닌, r, c과 병합된 셀을 모두 변경시켜주어야합니다.
- graph[51][51]을 돌면서 mergedX, mergedY가 r 과 c 일경우 해당 병합셀과 일치하므로 모두 변경시킵니다.
3. update value1 value2
//update value1 value2
else if(command.equals("UPDATE") && splitCommands.length == 3){
String value1 = splitCommands[1];
String value2 = splitCommands[2];
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].value.equals(value1)){ //UPDATE 시에 value1과 같은것을 발견한다면, value2로 모두 업데이트 시킵니다.
graph[k][j].value = value2;
}
}
}
}- 가장 단순한 명령어입니다.
- value1을 발견한다면 모두 value2 로 변경시켜주면됩니다.
- 이때, 병합셀을 고려하지않는 이유는 제 코드 상에서는 병합할때 value의 값도 모두 함께 병합합니다.
- 그렇기에, value값이 이미 업데이트 된 상항이기에 value1 값을 기반으로 찾는다면 병합된 값들이 모두 찾아집니다.
4. MERGE 1 2 1 3
else if(command.equals("MERGE")){
int r1 = Integer.parseInt(splitCommands[1]);
int c1 = Integer.parseInt(splitCommands[2]);
int r2 = Integer.parseInt(splitCommands[3]);
int c2 = Integer.parseInt(splitCommands[4]);
System.out.println(" "+r1+" "+c1+" "+r2+" "+c2);
if(graph[r1][c1].mergedX == graph[r2][c2].mergedX && graph[r1][c1].mergedY == graph[r2][c2].mergedY) continue;
if(r1 == r2 && c1 == c2) continue; // 같은 셀일 경우 무시
//기본 코드 조건 : 병합은 무조건 (r1, c1)으로 병합된다. 즉(r2, c2)가 잡아먹힙니다.
// 병합처리는 r1 c1을 기준으로 병합됩니다. (graph[r2][c2]가 변한다는 의미)
// r1 c1이 값을 가지고있을경우 r1 c1값으로 수정됩니다.
//조건1: graph[r1][c1]의 셀값이 존재하고, graph[r2][c2] 셀이 비어있을때
//조건2: graph[r1][c1]의 셀값이 존재하고, graph[r2][c2] 셀이 존재할때.
if( (graph[r1][c1].value.length() > 0 && graph[r2][c2].value.length() > 0) || ( graph[r1][c1].value.length() > 0 && graph[r2][c2].value.length() == 0 ) ) {
int originMergedX = graph[r2][c2].mergedX; //노드값이기에 변경될시 같이 변경됨. 참조로 되어있어서.
int originMergedY = graph[r2][c2].mergedY;
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].mergedX == originMergedX && graph[k][j].mergedY == originMergedY){
graph[k][j].value = graph[r1][c1].value;
graph[k][j].mergedX = graph[r1][c1].mergedX;
graph[k][j].mergedY = graph[r1][c1].mergedY;
// System.out.println("Working for 2 times: (k, j)"+k+" "+j);
}
}
}
}
//가장 유의해야할점은,
// 조건3 :graph[r1][c1]이 비어있고, graph[r2][c2] 값이 있는경우
// 조건4 :graph[r1][c1] 도 비어있고, graph[r2][c2]도 비어있는경우 ( 이때도 병합은 이루어집니다. )
else if( (graph[r1][c1].value.length() == 0 && graph[r2][c2].value.length() > 0 ) || (graph[r1][c1].value.length() == 0 && graph[r2][c2].value.length() == 0) ){
String originValue = graph[r2][c2].value;
int originMergedX = graph[r2][c2].mergedX; //노드값이기에 변경될시 같이 변경됨. 참조로 되어있어서.
int originMergedY = graph[r2][c2].mergedY;
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].mergedX == originMergedX && graph[k][j].mergedY == originMergedY){
graph[k][j].value = graph[r2][c2].value;
graph[k][j].mergedX = graph[r1][c1].mergedX;
graph[k][j].mergedY = graph[r1][c1].mergedY;
}
}
}
//조건3, 조건4 모두 graph[r1][c1]이 비어있는 경우를 의미합니다.
//graph[r1][c1]이 모두 비어있을경우 graph[r2][c2]값으로 값을 변경해주어야합니다.
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].mergedX == graph[r1][c1].mergedX && graph[k][j].mergedY == graph[r1][c1].mergedY){
graph[k][j].value = originValue;
}
}
}
}
}- 기본적으로 제 코드에서 지켜지는 조건입니다.
- 병합은 무조건 (r1, c1)으로 병합된다. 즉 graph[r2][c2]의 mergedX, mergedY가 graph[r1][c1]의 mergedX, mergedY로 갱신됩니다.
- graph[r1][c1] 이 값을 가지고있을경우 r1 c1값으로 수정됩니다.
- 병합은 graph[r1][c1]의 mergedX, mergedY로 이루어지지만 값은 graph[r1][c1] 뿐만 아니라 graph[r2][c2] 로도 변경될 수 있습니다.
- 분기처리
- 조건1: graph[r1][c1]의 셀값이 존재하고, graph[r2][c2] 셀이 비어있을때
- 조건2: graph[r1][c1]의 셀값이 존재하고, graph[r2][c2] 셀이 존재할때.
- 조건3 :graph[r1][c1]이 비어있고, graph[r2][c2] 값이 있는경우
- 조건4 :graph[r1][c1] 도 비어있고, graph[r2][c2]도 비어있는경우 ( 이때도 병합은 이루어집니다. 처음에 이걸 처리 안해서 찾는데 시간이 걸렸습니다. )
- 위의 분기처리에서 조건3, 조건4에서는 graph[r1][c1]값이 비어있기에 graph[r2][c2]의 값으로 전체 병합셀의 값을 수정시킵니다. ( 처음에 이걸 처리 안해서 찾는데 시간이 걸렸습니다. )
merge 에서 확인해보면 좋을 예시
["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", "MERGE 1 4 2 3", "UNMERGE 2 3", "MERGE 1 2 1 4", "MERGE 1 4 1 3", "MERGE 1 4 2 4", "MERGE 1 4 2 3"]
5. UNMERGED 1 4
else if(command.equals("UNMERGE")){
int r1 = Integer.parseInt(splitCommands[1]);
int c1 = Integer.parseInt(splitCommands[2]);
int mergedX = graph[r1][c1].mergedX;
int mergedY = graph[r1][c1].mergedY;
String beforeValue = graph[r1][c1].value;
for(int k=1;k<graph.length;k++){
for(int j=1;j<graph[k].length;j++){
if(graph[k][j].mergedX == mergedX && graph[k][j].mergedY == mergedY){
graph[k][j].mergedX = k;
graph[k][j].mergedY = j;
graph[k][j].value = "";
}
}
}
graph[r1][c1].value = beforeValue;
}- UNMERGED 하였을떄 병합된 셀의 모든 셀의 병합을 해제시킵니다.
- 만약 병합셀의 값이 있었다면, graph[r1][c1]의 셀의 값만 병합값으로 가져갑니다.
개인적으로 느꼈을때 문제에서 가장 유의해야하는 부분은,
MERGE 병합과정에서
1. 아무것도 없어도 병합이 되어야한다.
2. graph[r1][c1] graph[r2][c2]로 병합이 되었을때, graph[r2][c2]가 graph[r1][c1]으로 좌표는 병합되지만, value값 같은경우 graph[r1][c1]의 값이 없을경우 graph[r1][c1]의 병합셀들이 graph[r2][c2]의 값으로 병합됩니다.
위의 2가지 조건을 놓쳤었던 것이 시간소요에 많은 부분을 차지했습니다.
MERGE 과정에서의 4가지 조건을 이해하고, 코딩해야할 필요가 있습니다.
코드
import java.util.*;
class Solution {
public static Node[][] graph = new Node[51][51];
public static ArrayList<String> arr = new ArrayList<>();
String[] answer = {};
public String[] solution(String[] commands) {
for(int i=1; i<graph.length; i++){
for(int j=1; j<graph[i].length; j++){
graph[i][j] = new Node(i, j, "");
}
}
for(int i=0;i<commands.length;i++){
String[] splitCommands = commands[i].split(" ");
String command = splitCommands[0];
System.out.println(splitCommands[0]);
//update r c value
if(command.equals("UPDATE") && splitCommands.length == 4){
int r = Integer.parseInt(splitCommands[1]);
int c = Integer.parseInt(splitCommands[2]);
String value = splitCommands[3];
System.out.print(splitCommands[1]+" "+splitCommands[2]+" "+splitCommands[3]+" ");
graph[r][c].value = value;
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].mergedX == graph[r][c].mergedX && graph[k][j].mergedY == graph[r][c].mergedY){ //r c와 병합된 모든것들을 수정하기 위하여 입니다.
graph[k][j].value = graph[r][c].value;
}
}
}
}
//update value1 value2
else if(command.equals("UPDATE") && splitCommands.length == 3){
String value1 = splitCommands[1];
String value2 = splitCommands[2];
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].value.equals(value1)){ //UPDATE 시에 value1과 같은것을 발견한다면, value2로 모두 업데이트 시킵니다.
graph[k][j].value = value2;
}
}
}
}
else if(command.equals("MERGE")){
int r1 = Integer.parseInt(splitCommands[1]);
int c1 = Integer.parseInt(splitCommands[2]);
int r2 = Integer.parseInt(splitCommands[3]);
int c2 = Integer.parseInt(splitCommands[4]);
System.out.println(" "+r1+" "+c1+" "+r2+" "+c2);
if(graph[r1][c1].mergedX == graph[r2][c2].mergedX && graph[r1][c1].mergedY == graph[r2][c2].mergedY) continue;
if(r1 == r2 && c1 == c2) continue; // 같은 셀일 경우 무시
//기본 코드 조건 : 병합은 무조건 (r1, c1)으로 병합된다. 즉(r2, c2)가 잡아먹힙니다.
// 병합처리는 r1 c1을 기준으로 병합됩니다. (graph[r2][c2]가 변한다는 의미)
// r1 c1이 값을 가지고있을경우 r1 c1값으로 수정됩니다.
//조건1: graph[r1][c1]의 셀값이 존재하고, graph[r2][c2] 셀이 비어있을때
//조건2: graph[r1][c1]의 셀값이 존재하고, graph[r2][c2] 셀이 존재할때.
if( (graph[r1][c1].value.length() > 0 && graph[r2][c2].value.length() > 0) || ( graph[r1][c1].value.length() > 0 && graph[r2][c2].value.length() == 0 ) ) {
int originMergedX = graph[r2][c2].mergedX; //노드값이기에 변경될시 같이 변경됨. 참조로 되어있어서.
int originMergedY = graph[r2][c2].mergedY;
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].mergedX == originMergedX && graph[k][j].mergedY == originMergedY){
graph[k][j].value = graph[r1][c1].value;
graph[k][j].mergedX = graph[r1][c1].mergedX;
graph[k][j].mergedY = graph[r1][c1].mergedY;
// System.out.println("Working for 2 times: (k, j)"+k+" "+j);
}
}
}
}
//가장 유의해야할점은,
// 조건3 :graph[r1][c1]이 비어있고, graph[r2][c2] 값이 있는경우
// 조건4 :graph[r1][c1] 도 비어있고, graph[r2][c2]도 비어있는경우 ( 이때도 병합은 이루어집니다. )
else if( (graph[r1][c1].value.length() == 0 && graph[r2][c2].value.length() > 0 ) || (graph[r1][c1].value.length() == 0 && graph[r2][c2].value.length() == 0) ){
String originValue = graph[r2][c2].value;
int originMergedX = graph[r2][c2].mergedX; //노드값이기에 변경될시 같이 변경됨. 참조로 되어있어서.
int originMergedY = graph[r2][c2].mergedY;
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].mergedX == originMergedX && graph[k][j].mergedY == originMergedY){
graph[k][j].value = graph[r2][c2].value;
graph[k][j].mergedX = graph[r1][c1].mergedX;
graph[k][j].mergedY = graph[r1][c1].mergedY;
}
}
}
//조건3, 조건4 모두 graph[r1][c1]이 비어있는 경우를 의미합니다.
//graph[r1][c1]이 모두 비어있을경우 graph[r2][c2]값으로 값을 변경해주어야합니다.
for(int k=1; k<graph.length; k++){
for(int j=1; j<graph[k].length; j++){
if(graph[k][j].mergedX == graph[r1][c1].mergedX && graph[k][j].mergedY == graph[r1][c1].mergedY){
graph[k][j].value = originValue;
}
}
}
}
}
else if(command.equals("UNMERGE")){
int r1 = Integer.parseInt(splitCommands[1]);
int c1 = Integer.parseInt(splitCommands[2]);
int mergedX = graph[r1][c1].mergedX;
int mergedY = graph[r1][c1].mergedY;
String beforeValue = graph[r1][c1].value;
for(int k=1;k<graph.length;k++){
for(int j=1;j<graph[k].length;j++){
if(graph[k][j].mergedX == mergedX && graph[k][j].mergedY == mergedY){
graph[k][j].mergedX = k;
graph[k][j].mergedY = j;
graph[k][j].value = "";
}
}
}
graph[r1][c1].value = beforeValue;
}
else if(command.equals("PRINT")){
int r1 = Integer.parseInt(splitCommands[1]);
int c1 = Integer.parseInt(splitCommands[2]);
if(graph[r1][c1].value.length() == 0){
arr.add("EMPTY");
}else{
arr.add(graph[r1][c1].value);
}
}
}
answer = new String[arr.size()];
int idx = 0;
for(String a : arr){
answer[idx++] = a;
}
return answer;
}
}
class Node{
int mergedX; //병합코드의 ParentX
int mergedY; //병합코드의 ParentY
String value; //값 ( 비어있을시 "" )
public Node(int mergedX, int mergedY, String value){
this.mergedX = mergedX;
this.mergedY = mergedY;
this.value = value;
}
}'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 주사위 고르기 - 조합(Combination) + 브루트포스(BruteForce) + 이진탐색(Binary Search) JAVA (0) | 2024.03.19 |
|---|---|
| [프로그래머스] 가장 많이 받은 선물 - 구현(Implementation) + 2차원배열(two dimension array) + 해쉬맵(HashMap) JAVA (0) | 2024.03.04 |
| [프로그래머스]더 맵게 - 우선순위큐 (0) | 2023.02.25 |
| [프로그래머스]주식가격 - 구현 (0) | 2023.02.25 |
| [프로그래머스]프린터 - 큐 + arraylist (0) | 2023.02.15 |