[프로그래머스] 표 병합 - JAVA

in Algorithm on 구현

https://school.programmers.co.kr/learn/courses/30/lessons/150366

풀이

union-find를 이용한 구현 문제였다.

MERGE명령에 대한 설명을 읽고 union-find를 사용해야겠다고 생각했다. 병합된 셀의 어느 위치를 선택하더라도 병합된 셀로 접근한다는 부분에서 union-find에서 find를 해야겠다는 생각이 들었다.

parent 배열을 1차원으로 만들기 위해 2501사이즈의 배열로 만들었다. 표의 크기가 50X50이기 때문에 (r,c)의 좌표를 (r-1)X50+c로 바꿔 넣어줬다.

union-find 메소드들을 만들고 나서는 문제에 써있는대로 명령어들에 따른 기능을 구현했다.

주의할 점은 UNMERGE명령 중 find로 루트를 찾아 그 값을 루트로 갖는 셀들을 병합 해제해 주어야 하는데, 바로 parent를 i로 바꾸면 중간에 루트로 가지 못하는 셀들이 생긴다. 따라서, 1차로 같은 루트를 가진 셀들을 임시리스트에 넣어놓고 2차로 parent배열을 초기화해주었다.

메모리: 82.6MB

시간: 9.62ms

언어: Java 11

코드

import java.util.*;

class Solution {
    static int[] parent = new int[2501];
    static String[] table = new String[2501];
    static List<String> resultList;

    private static void init() {
        parent = new int[2501];
        table = new String[2501];
        resultList = new ArrayList<>();

        for(int i = 1; i < 2501; i++) {
            parent[i] = i;
            table[i] = "";
        }
    }

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

    private static void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        parent[py] = px;
    }

    public String[] solution(String[] commands) {
        init();

        for(String command : commands) {
            String[] line = command.split(" ");
            switch(line[0]) {
                case "UPDATE":
                    if(line.length == 4) {
                        updateOneCell(getCellNumber(line[1], line[2]), line[3]);
                    }else {
                        updateCellAtoB(line[1], line[2]);
                    }
                    break;

                case "MERGE":
                    mergeCell(getCellNumber(line[1], line[2]), getCellNumber(line[3], line[4]));
                    break;

                case "UNMERGE":
                    unMergeCell(getCellNumber(line[1], line[2]));
                    break;

                case "PRINT":
                    printCell(getCellNumber(line[1], line[2]));
                    break;
            }
        }

        String[] answer = resultList.toArray(new String[resultList.size()]);
        return answer;
    }

    // 셀 번호 변환. (2, 2) -> 52
    private static int getCellNumber(String a, String b) {
        int r = Integer.parseInt(a);
        int c = Integer.parseInt(b);

        return 50 * (r - 1) + c;
    }

    // 한 셀 바꾸기. 부모를 찾아서 바꾼다.
    private static void updateOneCell(int idx, String val) {
        table[find(idx)] = val;
    }

    // 같은 값인 모든 셀 바꾸기.
    private static void updateCellAtoB(String val1, String val2) {
        for(int i = 1; i < 2501; i++) {
            if(table[i].equals(val1)) {
                table[i] = val2;
            }
        }
    }

    // 셀 병합하기. 부모를 찾아 union한다. 값은 a에 넣고 b는 빈칸.
    private static void mergeCell(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if(rootA == rootB) {
            return;
        }

        String val = table[rootA];
        if(val.length() == 0) {
            val = table[rootB];
        }
        table[rootA] = val;
        table[rootB] = "";

        union(rootA, rootB);
    }

    // 병합 해제. 부모를 찾아서 같은 부모인 것들 리스트에 담아두고 병합 풀기.
    private static void unMergeCell(int idx) {
        int root = find(idx);
        String val = table[root];

        List<Integer> tmpList = new ArrayList<>();
        for(int i = 1; i < 2501; i++) {
            if(find(i) == root) {
                tmpList.add(i);
            }
        }

        for(Integer a : tmpList) {
            parent[a] = a;
        }

        table[root] = "";
        table[idx] = val;
    }

    // 출력 리스트에 담기.
    private static void printCell(int idx) {
        String val = table[find(idx)];
        if(val.length() == 0) {
            val = "EMPTY";
        }

        resultList.add(val);
    }

}