[프로그래머스] 표 병합

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150366

---

풀이

처음에는 사용자 정의 클래스를 이용해 풀었는데, 값이 난리가 나서 원시 자료형을 이용해 풀었다.
병합과 분할이라는 키워드를 보고, 유니온 파인드를 떠올렸다.

배열 선언하기

static int N = 50;
String[] table = new String[N*N+1];
int[] parent = new int[N*N+1];

 

각 셀은 자신의 값과, 부모 노드의 인덱스를 저장해야 한다.
따라서 값을 저장할 String 배열과, 병합된 셀의 인덱스를 저장하는 int형 배열을 선언해주었다.

표의 크기가 50x50으로 고정되어 있으므로 배열의 길이는 50*50+1 = 2501로 설정했다.

 

인덱스 변환 함수

int getIdx(int r, int c) {
    return (r-1)*N + c;
}
// r = idx/N + 1
// c = idx%N

 

맨 윗줄부터 1, 2, 3, ... , 2500의 인덱스를 가지므로 행과 열을 인덱스로 변환해주는 함수를 선언한다.

 

UPDATE

void updateCell(int r, int c, String value) {
    int rootIdx = find(getIdx(r, c));
    table[rootIdx] = value;
}

void updateValue(String value, String updatedValue) {
    for (int i=1; i<=N*N; i++) {
        if(table[i]!=null && table[i].equals(value)) {
            table[i] = updatedValue;
        }
    }
}

 

이제 문제에서 요구하는 기능들을 하나씩 구현해주면 된다.
셀의 개수가 그렇게 많지 않으므로 updateValue()에서는 따로 자료구조를 이용하지 않고, 전체 탐색을 이용했다.

 

MERGE

void merge(int r1, int c1, int r2, int c2) {
    int x = find(getIdx(r1, c1));
    int y = find(getIdx(r2, c2));

    // (r1, c1)과 (r2, c2)가 같은 셀인 경우 무시
    if(x==y) return;

    String value = table[x];
    if(table[x] == null) {
        value = table[y];
    }

    table[x] = null;
    table[y] = null;
    union(x, y);

    // 루트 셀에만 값 입력
    if(find(x) == x) {
        table[x] = value;
        table[y] = null;
    }
    else {
        table[x] = null;
        table[y] = value;
    }
}

 

(r2, c2)의 값으로 덮어씌우는 경우는 (r1, c1)이 빈 셀인 경우밖에 없음에 주의하자.
여러 셀이 병합된 경우, 루트 셀에만 값을 넣어주기 위해서 자식 셀의 값은 전부 null로 바꿔주었다.

 

UNMERGE

void unmerge(int r, int c) {
    int root = find(getIdx(r, c));
    String value = table[root];
    List<Integer> unmergeCells = new ArrayList<>();
    for (int i=1; i<=N*N; i++) {
        if(find(i) == root) {
            unmergeCells.add(i);
        }
    }

    for (int cell : unmergeCells) {
        parent[cell] = cell;
        table[cell] = null;
    }
    int idx = getIdx(r, c);
    table[idx] = value;
}

 

UNMERGE에서 주의해야 할 점은, 셀을 바로 분할해버리면 셀 간의 연결관계가 끊겨서 셀 분할이 제대로 진행되지 않는다는 점이다.

예를 들어 1, 5, 20, 28 총 네개의 셀이 병합된 상태라고 했을 때, 루트 셀은 1번 셀이 된다.
그런데 5번 셀을 바로 분할해버리면, parent[5] = 5가 되어, find(20)을 했을 때 5가 나오게 된다.

따라서 우리는 어떤 셀이 분할 대상인지 전부 확인한 뒤에 분할을 진행해야 한다.

 

PRINT

String print(int r, int c) {
    int root = find(getIdx(r, c));
    String value = table[root];

    if(value==null) return "EMPTY";
    else return value;
}

 

PRINT는 간단하다. 셀의 값이 null이면 EMPTY를, 그렇지 않으면 값을 반환해주면 된다.
이렇게 반환된 값은 리스트에 담아, 마지막에 배열로 변환하여 리턴했다.

 

---

전체 코드

import java.util.*;

class Solution {
    static int N = 50;
    String[] table = new String[N*N+1];
    int[] parent = new int[N*N+1];

    public String[] solution(String[] commands) {
        List<String> answer = new ArrayList<>();
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                int idx = getIdx(i, j);
                parent[idx] = idx;
            }
        }

        for (int i=0; i<commands.length; i++) {
            String[] command = commands[i].split(" ");
            if(command[0].equals("UPDATE") && command.length==3) {
                updateValue(command[1], command[2]);
            } else if(command[0].equals("MERGE")) {
                int r1 = Integer.parseInt(command[1]);
                int c1 = Integer.parseInt(command[2]);
                int r2 = Integer.parseInt(command[3]);
                int c2 = Integer.parseInt(command[4]);
                merge(r1, c1, r2, c2);
            } else {
                int r = Integer.parseInt(command[1]);
                int c = Integer.parseInt(command[2]);
                if(command[0].equals("UPDATE")) {
                    updateCell(r, c, command[3]);
                } else if (command[0].equals("UNMERGE")) {
                    unmerge(r, c);
                } else {
                    answer.add(print(r, c));
                }
            }
        }
        return answer.toArray(new String[answer.size()]);
    }

    int getIdx(int r, int c) {
        return (r-1)*N + c;
    }

    int find(int x) {
        int root = parent[x];
        if(root == x) return x;

        return parent[x] = find(parent[x]);
    }

    void updateCell(int r, int c, String value) {
        int rootIdx = find(getIdx(r, c));
        table[rootIdx] = value;
    }

    void updateValue(String value, String updatedValue) {
        for (int i=1; i<=N*N; i++) {
            if(table[i]!=null && table[i].equals(value)) {
                table[i] = updatedValue;
            }
        }
    }

    void union (int x, int y) {
        x = find(x);
        y = find(y);
        if(y < x) parent[x] = y;
        else parent[y] = x;
    }

    void merge(int r1, int c1, int r2, int c2) {
        int x = find(getIdx(r1, c1));
        int y = find(getIdx(r2, c2));

        if(x==y) return;

        String value = table[x];
        if(table[x] == null) {
            value = table[y];
        }

        table[x] = null;
        table[y] = null;
        union(x, y);

        if(find(x) == x) {
            table[x] = value;
            table[y] = null;
        }
        else {
            table[x] = null;
            table[y] = value;
        }
    }

    void unmerge(int r, int c) {
        int root = find(getIdx(r, c));
        String value = table[root];
        List<Integer> unmergeCells = new ArrayList<>();
        for (int i=1; i<=N*N; i++) {
            if(find(i) == root) {
                unmergeCells.add(i);
            }
        }

        for (int cell : unmergeCells) {
            parent[cell] = cell;
            table[cell] = null;
        }
        int idx = getIdx(r, c);
        table[idx] = value;
    }

    String print(int r, int c) {
        int root = find(getIdx(r, c));
        String value = table[root];

        if(value==null) return "EMPTY";
        else return value;
    }
}