프로그래머스 표 병합 자바 풀이

문제 요약

50 × 50 표에서 UPDATE, MERGE, UNMERGE, PRINT 명령을 순서대로 처리한다
MERGE는 두 셀을 하나로 합치고, 값이 있으면 그 값을 유지한다
UNMERGE는 선택한 셀이 속한 병합 그룹 전체를 원래 상태로 되돌린다
PRINT 결과들을 순서대로 배열에 담아 반환한다

문제 풀이

처음에는 병합된 셀들을 그룹(리스트)으로 따로 관리하면서, 병합될 때마다 그룹끼리 합치는 방식을 생각했다.

하지만 이 방식은 로직이 금방 꼬인다.

MERGE가 여러 번 중첩되면 어떤 셀이 어느 그룹에 속하는지 계속 갱신해야 하고, UNMERGE에서는 선택한 셀 하나가 아니라 그 병합 그룹 전체를 원래 상태로 되돌려야 해서 그룹 구조를 손으로 관리하기가 까다롭다.

이 문제의 핵심은 셀들의 연결 관계를 Union-Find(서로소 집합)로 관리하는 것이다.

각 셀을 parent 배열의 인덱스로 두고, 병합은 두 루트를 연결하는 union으로, 값 조회는 루트를 찾는 find로 처리하면 그룹 관리를 배열 하나로 끝낼 수 있다.

MERGE는 두 셀의 루트를 union하고, 값이 있는 쪽의 값을 루트에 남긴다
이때 중요한 점은, UNMERGE는 선택한 셀 하나만 분리하는 게 아니라 같은 루트를 공유하는 모든 셀을 찾아 각각 자기 자신을 부모로 되돌린다는 것이다
UNMERGE 이후에는 병합 그룹이 갖고 있던 값을 선택한 셀 하나에만 다시 넣는다
PRINT는 루트가 가진 값을 조회해서 비어 있으면 "EMPTY"를 담는다

최종 코드

java

import java.util.*;

class Solution {
    public int[] parent;
    public String[] values;
    
    // 경로 압축을 적용한 루트 찾기
    public int find(int a){
        if(parent[a] == a)
            return a;
        
        return parent[a] = find(parent[a]);
    }
    
    public void union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        
        if(pa==pb)
            return;
        
        String mergedValue;

        // 둘 중 값이 있는 쪽을 병합된 셀의 값으로 유지
        if (!values[pa].equals("")) {
            mergedValue = values[pa];
        } else {
            mergedValue = values[pb];
        }

        parent[pb] = pa;
        values[pa] = mergedValue;
        values[pb] = "";
    }
    
    public int toIdx(int r, int c){
        return (r-1)*50+(c-1);
    }
    
    public String[] solution(String[] commands) {
        List<String> ans = new ArrayList<>();
        parent = new int[50*50];
        values = new String[50*50];
        for(int i=0;i<2500;i++){
            parent[i] = i;
            values[i] = "";
        }
        
        for(int i=0;i<commands.length;i++){
            StringTokenizer st = new StringTokenizer(commands[i]);
            
            String op = st.nextToken();
            
            
            
            if("UPDATE".equals(op)){
                if(st.countTokens() == 3){
                    int r = Integer.parseInt(st.nextToken());
                    int c = Integer.parseInt(st.nextToken());
                    
                    int idx = toIdx(r,c);
                    
                    values[find(idx)] = st.nextToken();
                }else{
                    String value1 = st.nextToken();
                    String value2 = st.nextToken();
                    
                    for(int j=0;j<2500;j++){
                        if(value1.equals(values[j])){
                            values[j] = value2;
                        }
                    }
                }
                
            }else if ("MERGE".equals(op)){
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int r2 = Integer.parseInt(st.nextToken());
                int c2 = Integer.parseInt(st.nextToken());
                
                int idx = toIdx(r,c);
                int idx2 = toIdx(r2, c2);
                
                union(idx, idx2);
            }else if ("UNMERGE".equals(op)){
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int idx = toIdx(r,c);
                
                int root = find(idx);
                String value = values[root];
                
                // 같은 루트를 공유하는 병합 그룹의 멤버를 전부 찾는다
                List<Integer> members = new ArrayList<>();
                for(int j=0;j<2500;j++){
                    if(find(j) == root)
                        members.add(j);
                }
                
                // 그룹 전체를 초기 상태(자기 자신이 부모, 값 없음)로 되돌린다
                for(int m : members){
                    parent[m] = m;
                    values[m] = "";
                }
                
                values[idx] = value;
            }else{
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int idx = toIdx(r,c);
                
                int p = find(idx);
                if(!values[p].equals(""))
                    ans.add(values[p]);
                else
                    ans.add("EMPTY");
            }
        }
        
        String[] answer = new String[ans.size()];
        for(int i=0;i<ans.size();i++){
            answer[i] = ans.get(i);
        }
        return answer;
    }
}

표 병합

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기