Lv.3 표 병합 [JAVA]

문제링크-> 표 병합

성공 여부(걸린 시간): 성공(2일)

아이디어

처음에 문제를 풀때는 매우 순조로웠다. 각 기능인 update(2가지), merge, unmerge, print 총 5개의 함수를 구현하여
전체 명령문을 인자 반복문을 통해 수행해주며 마지막에 결과를 출력해주고자 했다.

 

함수별로 정리를 해볼 것인데 그전에 union-find를 통해 merge와 unmerge를 구현해주어야 다른 함수들도 제대로 동작할 수 있기에 union-Find 코드부터 작성을 해주었었다.

static int find(int x, int y){
        if(parent[x][y]==x*50+y){
            return x*50+y;
        }
        table[x][y] = null;
        return parent[x][y] = find(parent[x][y]/50, parent[x][y]%50);
    }
static void merge(int x, int y){//i*50+j 형식으로 받음
    int xP = find(x/50, x%50);
    int yP = find(y/50, y%50);
    if(xP == yP){
        return;
    }
    else{
        parent[yP/50][yP%50] = xP;
    }
}

 

일단 merge가 되었을때 제일 루트에만 해당 값을 저장해주거나 교체해주고 자식 노드들은 null을 저장한다.
이는 모든 기능을 거의 루트 기준으로 작동하는게 모든 방면에서 편하다고 생각된다. (문제 특성상)
그리고 나는 parent배열에는 부모를 x, y로 노드만들거나 int형 배열로 저장하기 싫어서
x * 50 + y를 해서 저장을 해주었는데

지금와서 생각해보니 이걸 table에도 적용하면 저렇게 귀찮게 변환하고 하는걸 줄일 수 있었을 것 같다.

 

1. UPDATE
업데이트는 2가지의 기능이 있는데 첫번째는 좌표 1개와 값이 주어져서
해당 좌표에 값을 업데이트 하는 기능 -> update1 함수(split했을때 인자가 4개)
해당 좌표의 부모노드를 find를 통해 찾고 그곳에 넣을 value를 넣어준다.

static void update1(int i, int j, String value){
    int num = find(i, j);
    table[num/50][num%50] = value;
}

 

그다음은 value1 value2가 주어지는 경우 -> update2 함수(3개)
단순 반복문으로 탐색하며 값을 찾으면 고치면 됨

static void update2(String target, String value){
    for(int i=0; i<50; i++){
        for(int j=0; j<50; j++){
            if(table[i][j]!=null&&table[i][j].equals(target)){
                table[i][j] = value;
            }
        }
    }
}

 

2. MERGE
병합에서는 호출전에 r1,c1을 x라하고 r2,c2를 y라 했을때
둘 중에서 값이 존재하는 곳에 다른게 붙는다.
만약 둘다 있다면 x에 y가 붙는다. 그것이 문제의 조건
그렇다면 둘중 루트가 될 좌표에 존재하는 String을 미리 temp로 빼놓고 다끝나고 루트에 넣어준다.
그래서 아래와 같이 merge를 호출하기 전에 미리 처리를 해주고 호출한다.

        //Main함수에서
        else if(command[0].equals("MERGE")){
                int targetX = find(Integer.parseInt(command[1])-1,Integer.parseInt(command[2])-1);
                int targetY = find(Integer.parseInt(command[3])-1,Integer.parseInt(command[4])-1);
                if(targetX==targetY){
                    continue;
                }
                String temp = table[targetX/50][targetX%50];
                if(table[targetX/50][targetX%50]==null){
                    temp = table[targetY/50][targetY%50];
                    int tp = targetX;
                    targetX = targetY;
                    targetY = tp;
                }
                merge(targetX, targetY);
                int num = find(targetX/50, targetX%50);
                table[num/50][num%50] = temp;
            }

 

호출이 되면 아까 설명한 merge와 같은 함수로 동작한다.(다르면 x를 부모로)

static void merge(int x, int y){//i*50+j 형식으로 받음
    int xP = find(x/50, x%50);
    int yP = find(y/50, y%50);
    if(xP == yP){
        return;
    }
    else{
        parent[yP/50][yP%50] = xP;
    }
}

 

3. UNMERGE
병합해제는 간단하게 루트 노드의 값을 임시로 가지고 있다가 전부 초기화해준 다음
해당하는 좌표에 넣어주면 끝이다.

그런데 이 부분에서 내가 2일동안 헤매게 만든 원인이 나온다.
바로 find를 통해 자신의 루트를 정확히 모르는 부분들을
놓친 것이다. 이부분을 추가하자마자 바로 성공했다.

static void unmerge(int x, int y){
        int group = find(x, y);
        for(int i=0; i<50; i++){// 경로압축을 통해 확실하게 루트 저장하게 하기 -> 안해서 2일 해맴 
            for(int j=0; j<50; j++){
                find(i,j);
            }
        }
        for(int i=0; i<50; i++){
            for(int j=0; j<50; j++){
                if(find(i, j)==group){
                    parent[i][j] = i*50+j;
                    table[i][j]=null;
                }
            }
        }
    }

 

4. PRINT
프린트 부분은 단순하게 부모를 찾아서 return해주면 된다.

static String print(int x, int y){
    int num = find(x, y);
    return table[num/50][num%50];
}

정답 코드

import java.util.*;
class Solution {
    static ArrayList<String> result;
    static String [][] table;
    static int [][] parent;// i*50+j로 숫자로 부모 저장 -> union find할떄 편하게 하기위함
    public String[] solution(String[] commands) {
        result = new ArrayList<>();
        table = new String[50][50];
        parent = new int[50][50];
        for(int i=0; i<50; i++){
            for(int j=0; j<50; j++){
                parent[i][j] = i*50+j;
                table[i][j] =null;
            }
        }
        for(String x : commands){
            String [] command = x.split(" ");
            if(command[0].equals("UPDATE")){
                if(command.length==4){ //좌표 - 값 update 1
                    int targetX = Integer.parseInt(command[1])-1;
                    int targetY = Integer.parseInt(command[2])-1;
                    update1(targetX, targetY, command[3]);
                }
                else{//값 - 값 update 2
                    update2(command[1], command[2]);
                }
            }
            else if(command[0].equals("MERGE")){
                int targetX = find(Integer.parseInt(command[1])-1,Integer.parseInt(command[2])-1);
                int targetY = find(Integer.parseInt(command[3])-1,Integer.parseInt(command[4])-1);
                if(targetX==targetY){
                    continue;
                }
                String temp = table[targetX/50][targetX%50];
                if(table[targetX/50][targetX%50]==null){
                    temp = table[targetY/50][targetY%50];
                    int tp = targetX;
                    targetX = targetY;
                    targetY = tp;
                }
                merge(targetX, targetY);
                int num = find(targetX/50, targetX%50);
                table[num/50][num%50] = temp;
            }
            else if(command[0].equals("UNMERGE")){
                int targetX = Integer.parseInt(command[1])-1;
                int targetY = Integer.parseInt(command[2])-1;
                String temp = print(targetX, targetY);
                unmerge(targetX, targetY);
                table[targetX][targetY] = temp;
            }
            else if(command[0].equals("PRINT")){
                int targetX = Integer.parseInt(command[1])-1;
                int targetY = Integer.parseInt(command[2])-1;
                String printString = print(targetX, targetY)==null? "EMPTY":print(targetX, targetY);
                result.add( printString);
            }
        }
        //마지막에 결과 반환
        String[] answer = new String[result.size()];
        for(int i=0; i<result.size(); i++){
            answer[i] = result.get(i);
        }
        return answer;
    }
    static int find(int x, int y){
        if(parent[x][y]==x*50+y){
            return x*50+y;
        }
        table[x][y] = null;
        return parent[x][y] = find(parent[x][y]/50, parent[x][y]%50);
    }
    static void merge(int x, int y){ //i*50+j 형식으로 받음
        int xP = find(x/50, x%50);
        int yP = find(y/50, y%50);
        if(xP == yP){
            return;
        }
        else{
            parent[yP/50][yP%50] = xP;
        }
    }
    static void update1(int i, int j, String value){
        int num = find(i, j);
        table[num/50][num%50] = value;
    }
    static void update2(String target, String value){
        for(int i=0; i<50; i++){
            for(int j=0; j<50; j++){
                if(table[i][j]!=null&&table[i][j].equals(target)&&parent[i][j]==i*50+j){
                    table[i][j] = value;
                }
            }
        }
    }
    static void unmerge(int x, int y){
        int group = find(x, y);
        for(int i=0; i<50; i++){
            for(int j=0; j<50; j++){
                find(i,j);
            }
        }
        for(int i=0; i<50; i++){
            for(int j=0; j<50; j++){
                if(find(i, j)==group){
                    parent[i][j] = i*50+j;
                    table[i][j]=null;
                }
            }
        }
    }
    static String print(int x, int y){
        int num = find(x, y);
        return table[num/50][num%50];
    }
}