[프로그래머스 Level.3] 표 병합 (2023 KAKAO BLIND RECRUITMENT) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT > 표 병합

 

 

문제 설명

 

 

당신은 표 편집 프로그램을 작성하고 있습니다.

표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

 

1. "UPDATE r c value"
   • (r, c) 위치의 셀을 선택합니다.
   • 선택한 셀의 값을 value로 바꿉니다.
2. "UPDATE value1 value2"
   • value1을 값으로 가지고 있는 모든 셀을 선택합니다.
   • 선택한 셀의 값을 value2로 바꿉니다.
3. "MERGE r1 c1 r2 c2"
   
   • (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
   • 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
   • 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
   • 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
   • 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
   • 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
4. "UNMERGE r c"
   • (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
   • 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
   • 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
5. "PRINT r c"
   • (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
   • 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

 

아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.

 

commands	효과
UPDATE 1 1 menu	(1,1)에 "menu" 입력
UPDATE 1 2 category	(1,2)에 "category" 입력
UPDATE 2 1 bibimbap	(2,1)에 "bibimbap" 입력
UPDATE 2 2 korean	(2,2)에 "korean" 입력
UPDATE 2 3 rice	(2,3)에 "rice" 입력
UPDATE 3 1 ramyeon	(3,1)에 "ramyeon" 입력
UPDATE 3 2 korean	(3,2)에 "korean" 입력
UPDATE 3 3 noodle	(3,3)에 "noodle" 입력
UPDATE 3 4 instant	(3,4)에 "instant" 입력
UPDATE 4 1 pasta	(4,1)에 "pasta" 입력
UPDATE 4 2 italian	(4,2)에 "italian" 입력
UPDATE 4 3 noodle	(4,3)에 "noodle" 입력

 

 

위 명령어를 실행하면 아래 그림과 같은 상태가 됩니다.

 

 

아래는 MERGE 명령어를 실행하여 셀을 병합하는 예시입니다.

 

commands	효과
MERGE 1 2 1 3	(1,2)와 (1,3) 병합
MERGE 1 3 1 4	(1,3)과 (1,4) 병합

 

 

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

 

병합한 셀은 "category" 값을 가지게 되며 (1,2), (1,3), (1,4) 중 어느 위치를 선택하더라도 접근할 수 있습니다.

 

 

아래는 UPDATE 명령어를 실행하여 셀의 값을 변경하는 예시입니다.

commands	효과
UPDATE korean hansik	"korean"을 "hansik"으로 변경
UPDATE 1 3 group	(1,3) 위치의 셀 값을 "group"으로 변경

 

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

 

 

아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.

 

commands	효과
UNMERGE 1 4	셀 병합 해제 후 원래 값은 (1,4)가 가짐

 

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

 

 

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

---

제한사항

• 1 ≤ commands의 길이 ≤ 1,000
• commands의 각 원소는 아래 5가지 형태 중 하나입니다.
  1. "UPDATE r c value"
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
     • value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
  2. "UPDATE value1 value2"
     • value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
  3. "MERGE r1 c1 r2 c2"
     
     • r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  4. "UNMERGE r c"
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  5. "PRINT r c"
     
     • r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
• commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.

 

---

 

입출력 예

commands	result
["UPDATE 1 1 menu", "UPDATE 1 2 category", "UPDATE 2 1 bibimbap", "UPDATE 2 2 korean", "UPDATE 2 3 rice", "UPDATE 3 1 ramyeon", "UPDATE 3 2 korean", "UPDATE 3 3 noodle", "UPDATE 3 4 instant", "UPDATE 4 1 pasta", "UPDATE 4 2 italian", "UPDATE 4 3 noodle", "MERGE 1 2 1 3", "MERGE 1 3 1 4", "UPDATE korean hansik", "UPDATE 1 3 group", "UNMERGE 1 4", "PRINT 1 3", "PRINT 1 4"]	["EMPTY", "group"]
["UPDATE 1 1 a", "UPDATE 1 2 b", "UPDATE 2 1 c", "UPDATE 2 2 d", "MERGE 1 1 1 2", "MERGE 2 2 2 1", "MERGE 2 1 1 1", "PRINT 1 1", "UNMERGE 2 2", "PRINT 1 1"]	["d", "EMPTY"]

 

---

입출력 예 설명

 

입출력 예 #1

• 문제 예시와 같습니다. (1,3) 위치의 셀은 비어있고 (1,4) 위치의 셀 값은 "group"입니다. 따라서 ["EMPTY", "group"]을 return 해야 합니다.

 

입출력 예 #2

• 모든 UPDATE 명령어를 실행하면 아래와 같은 상태가 됩니다.

 

• "MERGE 1 1 1 2" 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "MERGE 2 2 2 1" 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "MERGE 2 1 1 1" 명령어를 실행하면 아래와 같은 상태가 됩니다.

• "UNMERGE 2 2" 명령어를 실행하면 아래와 같은 상태가 됩니다.

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    int[][] parent;
    public String[] solution(String[] commands) {
        String[] answer = {};

        ArrayList<String> resultList = new ArrayList<>();
        
        String[][] matrix = new String[51][51];
        
        parent = new int[51][51];
        
        for(int i=1; i<parent.length; i++) {
            for(int j=1; j<parent[0].length; j++) {
                parent[i][j] = i*100 + j;
            }
        }

        for(int i=0; i<commands.length; i++) {
            String[] commandArr = commands[i].split(" ");
            if("UPDATE".equals(commandArr[0])) {
                if(commandArr.length == 4) {
                    int r = Integer.parseInt(commandArr[1]);
                    int c = Integer.parseInt(commandArr[2]);
                    int parentVal = findParent(r, c);
                    matrix[parentVal/100][parentVal%100] = commandArr[3]; // 부모의 좌표를 업데이트
                } else {
                    for(int j=1; j<matrix.length; j++) {
                        for(int k=1; k<matrix[0].length; k++) {
                            if(commandArr[1].equals(matrix[j][k]) && findParent(j, k) == j*100 + k) // value1이고 자신이 부모이면 업데이트
                                matrix[j][k] = commandArr[2];
                        }
                    }
                }
            } else if("MERGE".equals(commandArr[0])) {
                int r1 = Integer.parseInt(commandArr[1]);
                int c1 = Integer.parseInt(commandArr[2]);
                int r2 = Integer.parseInt(commandArr[3]);
                int c2 = Integer.parseInt(commandArr[4]);

                int parentVal1 = findParent(r1, c1);
                int parentVal2 = findParent(r2, c2);
                
                if(parentVal1 == parentVal2) continue; // 부모가 같으면 이미 MERGE 상태
                
                if(matrix[parentVal1/100][parentVal1%100] == null) {
                    parent[parentVal1/100][parentVal1%100] = parentVal2;
                } else {
                    parent[parentVal2/100][parentVal2%100] = parentVal1;
                }
            } else if("UNMERGE".equals(commandArr[0])) {
                int r = Integer.parseInt(commandArr[1]);
                int c = Integer.parseInt(commandArr[2]);

                int parentVal = findParent(r, c);
                String mergedVal = matrix[parentVal/100][parentVal%100];
                
                ArrayList<Integer> unmergeList = new ArrayList<>();
                for(int j=1; j<parent.length; j++) {
                    for(int k=1; k<parent.length; k++) {
                        if(findParent(j, k) == parentVal) {
                            unmergeList.add(j*100 + k);
                        }
                    }
                }
                
                for(int u : unmergeList) {
                    parent[u/100][u%100] = u;
                    matrix[u/100][u%100] = null;
                }
                matrix[r][c] = mergedVal;
            } else if("PRINT".equals(commandArr[0])) {
                int r = Integer.parseInt(commandArr[1]);
                int c = Integer.parseInt(commandArr[2]);
                int parentVal = findParent(r, c);

                String printStr = matrix[parentVal/100][parentVal%100] == null ? "EMPTY" : matrix[parentVal/100][parentVal%100];
                resultList.add(printStr);
            }
        }
        
        answer = new String[resultList.size()];

        for(int i=0; i<resultList.size(); i++) {
            answer[i] = resultList.get(i);
        }
        
        return answer;
    }
    
    public int findParent(int i, int j) {
        if(parent[i][j] == i*100 + j)
            return i*100 + j;

        return findParent(parent[i][j]/100, parent[i][j]%100);
    }
}

 

풀이

1. 이 문제는 명령에 따라서 해당 표을 바로 수정하면서 풀기 보단 parent 배열을 생성하여 union-find를 이용해서 명령이 주어지면 parent 배열에 적용해서 표의 셀을 연결하고 해제하며 값을 변경하여 풀어야 한다.
2.  우선 표를 나타내기 위한 String형 2차원 배열 matrix와 셀의 연결을 나타내기 위한 int형 2차원 배열 parent를 생성한다.
3. parent 배열은 처음에 자기 자신을 바라보도록 초기화 하는데 2차원 배열이므로 고유한 수로 나타내기 위해 i * 100 + j로 하여 겹치는 수가 없도록 만든다.
4. 이제 commands를 순회하면서 주어진 명령대로 수행하도록 한다.
   1. "UPDATE r c value" 형태라면 (r, c) 위치의 값을 value로 수정해야한다. (r, c) 좌표는 부모 좌표를 바로보고 있으므로 (r, c)의 부모 좌표를 찾아 해당 부모 좌표의 값을 value로 업데이트 한다.
   2. "UPDATE value1 value2" 형태라면 value1을 값으로 가지고 있는 모든 셀을 value2로 업데이트 해야 한다. 따라서 value1을 값으로 가지고 있으면서 자기 자신을 바라보고 있는 좌표를 찾아 해당 셀의 값을 value2로 업데이트 한다.
   3. "MERGE r1 c1 r2 c2" 형태라면 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 병합하고 값을 가지고 있는 셀의 값을 가져야 한다. 따라서 (r1, c1)의 부모 좌표와 (r2, c2)의 부모 좌표를 찾고 혹시 이미 부모 좌표가 같다면 이미 같은 셀이므로 넘어가고 아니라면 병합하면 된다. matrix에서 두 부모 좌표의 값을 확인하여 (r1, c1)의 부모 좌표의 값이 비어있다면 (r1, c1)의 부모 좌표가 (r2, c2)이 부모 좌표를 바라보도록 하고 (r1, c1)의 부모 좌표의 값이 있다면 (r2, c2)의 부모 좌표가 (r1, c1)의 부모 좌표를 바라보도록 하여 하나의 부모 좌표를 바라보도록 셀을 병합한다.
   4. "UNMERGE r c" 형태라면 (r, c) 위치의 셀의 모든 병합을 해제해야 한다. 따라서 (r, c)의 부모 좌표를 찾고 해당 부모 좌표가 가지고 있는 값을 임시로 저장한다. 그리고 병합을 해제할 위치의 셀들을 담기 위해 ArrayList를 생성하고 parent 배열을 모두 순회하면서 최종 부모 좌표가 (r, c)의 부모 좌표인 좌표들을 찾아 ArrayList에 담는다. 이제 ArrayList를 다시 순회하면서 해당 셀들의 부모 좌표를 자기 자신으로 변경하고 해당 셀들의 값을 비어있는 상태(null)로 변경한다. 그리고 (r, c) 위치의 셀의 값을 임시로 저장했던 값을 가져와 저장하여 병합을 해제하기 전에 갖던 값을 (r, c)가 값을 갖게 하면 된다.
      (parent 배열을 순회하면서 바로 병합을 해제하지 않고 ArrayList에 담았다가 다시 ArrayList를 순회하면서 병합을 해제하는 이유는 parent 배열을 순회할 때 병합을 해제하면 최종 부모 좌표까지 도달하기 전에 중간에 병합을 해제한 셀이 생겨서 연결이 꼬이게 되기 때문이다. 예를들어 (3, 4)의 부모가 (2, 3)이고 (2, 3)의 부모가 (5, 6)이고 (5, 6)의 부모가 (5, 6)으로 자기 자신이라면 최종 부모가 (5, 6)이 된다. parent 배열을 순회하면서 (2, 3)의 부모가 (5, 6)이므로 병합을 해제하여 (2, 3)은 자기자신을 바라보고 있게 된 후에 (3, 4)의 부모가 (2, 3)이고 (2, 3)의 부모는 자기자신이 되어있는 상태이므로 (5, 6)이 아니기때문에 (2, 3)은 병합을 해제하지 않고 (2, 3)을 바라보고 있는 상태로 남겨져서 병합이 모두 해제가 되지 않는 상태가 된다. 그러므로 최종 부모가 (5, 6)을 바라보고 있는 (2, 3), (3, 4), (5, 6)을 모두 ArrayList에 담고 해당 좌표들을 순회하면서 병합을 해제하는 것이다)
   5. "PRINT r c" 형태라면 (r, c) 위치의 셀의 값을 출력하면 된다. 따라서 (r ,c)의 부모 좌표를 찾아 해당 부모 좌표가 가지고 있는 값을 resultList에 담아주면 된다. 만약 해당 부모 좌표의 값이 비어 있다면(null 이라면) "EMPTY"를 담아주면  된다.
5. 출력할 데이터들을 resultList에 담았으므로 resultList를 순회하면서 answer에 저장하고 반환하면 된다.