[프로그래머스/Java] [Kakao 블라인드 기출] 표 병합

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

프로그래머스

 

 

💬 회고점

일반적인 구현 문제였지만, MERGE 명령어를 구현하는 과정에서 많은 시간이 소요되었습니다. 최종적으로는 union 기법을 활용해 MERGE의 내용을 구현했고, MERGE에서 둘 중 하나만 값을 가지고 있으면 그 값으로 업데이트 하는 것에서 로직 오류가 있었습니다. 해당 오류를 고치는 과정에서도 시간이 걸렸습니다. 

 

결국 원인을 찾아서 해결했지만,

union 기법을 다양하게 활용할 수 있다는 생각을 들게 해주는 문제였고 테스트도 좀 더 꼼꼼히 하며 문제를 해결해야겠다는 생각이 들었습니다.

 

---

✏️ 코드

import java.util.*;

class Solution {

    private static final int MAX = 50;

    private int[] parent = new int[MAX * MAX];
    private String[][] board = new String[MAX][MAX];

    public List<String> solution(String[] commands) {
        List<String> answer = new ArrayList<>();
        initParent();
        initBoard();

        for (String command : commands) {
            String[] c = command.split(" ");

            if ("PRINT".equals(c[0])) {
                answer.add(print(c[1], c[2]));
                continue;
            }

            if ("UPDATE".equals(c[0])) {
                int size = c.length;

                if (size == 3) {
                    switchValue(c[1], c[2]);

                } else {
                    updateTarget(c[1], c[2], c[3]);
                }
                continue;
            }

            if ("MERGE".equals(c[0])) {
                doMerge(c[1], c[2], c[3], c[4]);
                continue;
            }

            if ("UNMERGE".equals(c[0])) {
                doUnmerge(c[1], c[2]);
                continue;
            }

        }

        return answer;
    }

    private void doUnmerge(String r, String c) {
        int r_int = Integer.parseInt(r) - 1;
        int c_int = Integer.parseInt(c) - 1;
        int ori_parent = parent[MAX * r_int + c_int];
        String keep = board[r_int][c_int];
        for (int i = 0; i < MAX; ++i) {
            for (int j = 0; j < MAX; ++j) {
                if (parent[MAX * i + j] == ori_parent) {
                    board[i][j] = "EMPTY";
                    parent[MAX * i + j] = MAX * i + j;
                }
            }
        }
        board[r_int][c_int] = keep;
    }

    private void doMerge(String originR, String originC,
                         String otherR, String otherC) {
        if (originR.equals(otherR) && originC.equals(otherC)) {
            return;
        }

        int ori_r = Integer.parseInt(originR) - 1;
        int ori_c = Integer.parseInt(originC) - 1;
        int otr_r = Integer.parseInt(otherR) - 1;
        int otr_c = Integer.parseInt(otherC) - 1;
        String inputValue;
        boolean flag = true;
        int ori_parent = parent[MAX * ori_r + ori_c];
        int otr_parent = parent[MAX * otr_r + otr_c];

        if (parent[ori_parent] == parent[otr_parent]) {
            return;
        }

        if ("EMPTY".equals(board[ori_r][ori_c]) && !"EMPTY".equals(board[otr_r][otr_c])) {
            inputValue = board[otr_r][otr_c];
            flag = false;
        } else  {
            inputValue = board[ori_r][ori_c];
        }
        parent[otr_parent] = ori_parent;
        board[otr_r][otr_c] = inputValue;
        board[otr_parent / MAX][otr_parent % MAX] = inputValue;

        for (int i = 0; i < MAX; ++i) {
            for (int j = 0; j < MAX; ++j) {
                int idx = MAX * i + j;
                if (flag && parent[idx] == otr_parent) {
                    parent[idx] = ori_parent;
                    board[i][j] = inputValue;
                } else if (!flag && parent[idx] == ori_parent) {
                    board[i][j] = inputValue;
                } else if (!flag && parent[idx] == otr_parent) {
                    parent[idx] = ori_parent;
                }
            }
        }
    }

    private void updateTarget(String r, String c, String value) {
        int r_int = Integer.parseInt(r) - 1;
        int c_int = Integer.parseInt(c) - 1;
        int ori_parent = parent[MAX * r_int + c_int];

        board[r_int][c_int] = value;

        for (int i = 0; i < MAX; ++i) {
            for (int j = 0; j < MAX; ++j) {
                if (parent[MAX * i + j] == ori_parent) {
                    board[i][j] = value;
                }
            }
        }
    }

    private void switchValue(String from, String to) {
        for (int i = 0; i < MAX; ++i) {
            for (int j = 0; j < MAX; ++j) {
                if (from.equals(board[i][j])) {
                    board[i][j] = to;
                }
            }
        }
    }

    private String print(String r, String c) {
        return board[Integer.parseInt(r) - 1][Integer.parseInt(c) - 1];
    }

    private void initBoard() {
        for (int i = 0; i < MAX; ++i) {
            for (int j = 0; j < MAX; ++j) {
                board[i][j] = "EMPTY";
            }
        }
    }

    private void initParent() {
        for (int i = 0; i <= MAX * MAX - 1; ++i) {
            parent[i] = i;
        }

    }
}