[코딩테스트 연습] 표 병합

🔍 난이도 : Lv.3
🔤 언어 : java
📎 문제 링크 : 표 병합

첫 풀이(코드 생략)

• 조건에 따른 빡 구현인줄 알았으나, 예제만 맞지 구현은 실패했다.
• 여기 문제에서 중요한것은 병합된 상태를 기억해야된다는 것! 즉, 유니온 파인드를 생각해내는 것이 포인트였다!
  • 확실히..오랜만에 한게 티남..🤦‍♂️

두번째 풀이

• 유니온파인드를 생각하여, 다시 설계하였다.

  • 이전 기록 참조

• 먼저 50*50 테이블을 만들어 각각 번호를 넣어준다. 0~2499번까지

  • Update

    • 값 기입일 유니온파인드 parent[][] 배열에서 같은 값 경우 다 기입
    • 값 변경일 경우 아래과정을 진행
      1. 원래 배열의 동일한 value 위치 다 찾는다.
      2. 해당 위치의 parent[][] 값을 보고 동일한 값 위치 다 찾는다.
      3. 변경할 value로 바꿔준다.

  • Merge

    1. 병합할 parnt값을 비교하고 더 작은 값으로 같을 채운다.
    2. 테이블을 비교하여 값을 넣는데, 여기서 중요한것은 r1, c1 의 값의 우선순위 먼저라는 것이다.
    3. 추후 다른 연결된 장소는 부모를 찾으면서 부모의 값을 따라 적용하면 된다.

  • UnMerge

    1. table에서 r,c 위치의 value를 백업해놓는다.
    2. parent 배열에 r,c 위치의 값이 무엇인지 알아낸다. =result
    3. 기본적으로 완전 탐색하여,parent 배열에서 부모노드를 찾는다. 찾는 과정에서 result값과 동일하다면 table값을 전부 삭제한다.
    4. 또한, parent도 고유의 위치값으로 초기화한다.
    5. 그리고 마지막으로 table의 r,c 위치의 값만 value로 넣어준다.

  • Print

    • 해당위치의 값을 출력하면 된다.

실패한 코드(40.9점)

import java.util.*;

class Solution {
    int[] parent;
    String[] table;
    List<String> result;

    public String[] solution(String[] commands) {
        parent = new int[2500];
        table = new String[2500];
        result = new ArrayList<>();
        for (int i = 1; i < 2500; i++) {
            parent[i] = i;
        }

        for (String cmd : commands) {
            commandResolver(cmd);
        }


        String[] answer = new String[result.size()];
        int idx = 0;
        for (String str : result) {
            answer[idx] = str;
            idx++;
        }

        return answer;
    }

    private void commandResolver(String str) {
        String[] cmdArr = str.split(" ");
        String cmd = cmdArr[0];
        int len = 0;
        int r = 0;
        int c = 0;
        int r2 = 0;
        int c2 = 0;
        String val1 = "";
        String val2 = "";

        if (cmd.equals("UPDATE")) {
            len = cmdArr.length;
            if (len == 4) {
                //해당 위치에 값 기입
                r = Integer.parseInt(cmdArr[1]);
                c = Integer.parseInt(cmdArr[2]);
                val1 = cmdArr[3];
                updateRCvalue(makeParentIndex(r, c), val1);
            }
            // 모든 값 바꾸기
            if (len == 3) {
                val1 = cmdArr[1];
                val2 = cmdArr[2];
                updateChageValue(val1, val2);
            }
            return;
        }
        r = Integer.parseInt(cmdArr[1]);
        c = Integer.parseInt(cmdArr[2]);

        if (cmd.equals("MERGE")) {
            r2 = Integer.parseInt(cmdArr[3]);
            c2 = Integer.parseInt(cmdArr[4]);
            mergeTwoRC(makeParentIndex(r, c), makeParentIndex(r2, c2));
        }
        if (cmd.equals("UNMERGE")) {
            unMerge(makeParentIndex(r, c));
        }
        if (cmd.equals("PRINT")) {
            printValue(makeParentIndex(r, c));
        }
        return;
    }

    private void updateRCvalue(int x, String val) {
        //해당 위치의 parent값과 동일한지 찾기
        table[getParent(x)] = val;
        // ArrayList<Integer> list = getSameParentList(x);
        // for(int idx : list){
        //     table[idx] = val;
        // }
    }

    private void updateChageValue(String val1, String val2) {
        ArrayList<Integer> list = getSameValueList(val1);
        for (int idx : list) {
            updateRCvalue(idx, val2);
        }
    }

    private void mergeTwoRC(int x1, int x2) {
        String str = null;
        if (table[getParent(x1)] != null) {
            str = table[getParent(x1)];
        } else {
            str = table[getParent(x2)];
        }
        table[getParent(x1)] = null;
        table[getParent(x2)] = null;
        int idx = unionParent(x1, x2);
        
        table[idx] = str;
    }

    private void unMerge(int x) {
        String str = table[getParent(x)];
        int t = getParent(x);

        for (int i = 0; i < 2500; i++) {
            if (findParent(t, i)) {
                //초기화
                table[i] = null;
                parent[i] = i;
            }
        }
        table[x] = str;

    }

    private void printValue(int x) {
        int idx = getParent(x);
        if (table[idx] == null) {
            result.add("EMPTY");
            return;
        }
        result.add(table[idx]);
    }


    private ArrayList<Integer> getSameValueList(String val) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 2500; i++) {
            if (table[i] == null) continue;
            if (table[i].equals(val)) {
                list.add(i);
            }
        }
        return list;
    }


    private ArrayList<Integer> getSameParentList(int x) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 2500; i++) {
            if (findParent(x, i)) {
                list.add(i);
            }
        }

        return list;
    }

    private int getParent(int x) {
        if (parent[x] == x) {
            return x;
        }
        return getParent(parent[x]);
    }

    // 합치기
    private int unionParent(int x, int y) {
        x = getParent(x);
        y = getParent(y);
        if (x > y) parent[x] = y;
        else parent[y] = x;
        return parent[x];
    }

    // 조회
    private boolean findParent(int x, int y) {
        x = getParent(x);
        y = getParent(y);
        return x == y;
    }

    // r, c 조회
    private int[] getCoordinate(int x) {
        int r = x / 50;
        int c = x % 50;
        return new int[]{r, c};
    }

    private int makeParentIndex(int r, int c) {
        return r * 50 + c;
    }

}

• 어느정도 통과는 했으나, 2번과 13번은 실패, 나머지는 런타임에러가 났다.

원인분석

• 아직 명확하진 않으나 유니온 파인드 활용면에서 효율이 좋지 못한 것 같다.
• 게다가 실패도 있으니 조건을 먼가 빠트린게 있는 듯 하다.