[코딩테스트 연습] 표 병합2

신창호·2023년 10월 9일

프로그래머스코딩 문제

목록 보기

8/8

🔍 난이도 : Lv.3
🔤 언어 : java
📎 문제 링크 : 표 병합

세번째 풀이

조건 다시 확인

먼저 Merge조건 부터 확인해보자!
- (r1,c1)위치의 셀과 (r2,c2)위치셀을 합친다.
- 이때 한셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지고, 둘다 갖고있다면, (r1,c1)위치의 값을 가지게 된다.
  - 여기서 이전 조건 value가 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열이기 때문에 ""이 올 수 없다. 즉 값이 있다면 길이가 1이상인 문자열이 있고, 없다면 null이라는 것이다.
- 그리고 이후 (r1,c1)이든 (r2,c2)이든 어느 위치를 선택해도 병합된 셀에 접근해야된다.
```
    private void mergeTwoRC(int x1, int x2) {
      String str = null;
      if (table[getParent(x1)] != null) {
          str = table[getParent(x1)];
      } else {
          str = table[getParent(x2)];
      }
      int idx = unionParent(x1, x2);
      table[idx] = str;
  }
```
아무런 이상이 없어 보인다.
그다음은, unMerge 조건이다.
- (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제한다.
  - 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태
  - 즉, union으로 변경된 값들을 원래상태로 되돌리면 된다.
- 합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값만 가지면 된다.

	private void unMerge(int x) {
        String str = table[getParent(x)];
        int t = getParent(x);

        for (int i = 0; i < 2500; i++) {
            if (findParent(t, i)) {
                //초기화
                table[i] = null;
                parent[i] = i;
            }
        }
        table[x] = str;

	}

여기서 이전 코드를 보니 문제가 하나 발생했다. 만약 parent의 값들이 [0, 1, 1, 2]이라고 할때,
첫번째 빼고 모든 값들은 다 1을 가리키는 형태라 할 수 있다.
- 인덱스 0 -> 0
- 인덱스 1 -> 1
- 인덱스 2 -> 1
- 인덱스 3 -> 2 -> 1
인덱스 1과2는 1을 가리키기때문에 같은 값이지만, 인덱스 3의 경우도 2를 가리키고, 2는 1을 가리키기때문에 모두 1로 병합되어 있다 볼 수 있다.
하지만 위 코드는 아래서 부터 초기화를 하기때문에 결과는 [0,1,2,2]가 되어 버린다. 즉, 인덱스 3은 1과 같다고 인식되지 않아 버린다는 것이다.

private void unMerge(int x) {
        String str = table[getParent(x)];
        int t = getParent(x);

        for (int i = 2499; i >= 0; i--) {
            if (findParent(t, i)) {
                //초기화
                table[i] = null;
                parent[i] = i;
            }
        }
        table[x] = str;

    }

그래서 해결책은 값을 뒤에서 부터 시작해주면 된다

실패한코드(50.0점)

하지만 아직 런타임 에러는 해결하지 못했다.

원인분석

먼가 null값이 잘못들어가는 것이 아닐까?
잠깐 자리를 옮겨 고민을 해보니, index가 먼가 이상함을 느꼈다.

    private int makeParentIndex(int r, int c) {
        return r * 50 + c;
    }

애초에 이 코드는 (1,1)이여도 51부터 시작하는 것이였다.
또, 처음 만든 코드도 new int[2500];로 만들어 하나가 부족한 것이다. 이로인해 아래와 같이 수정했고

    private int makeParentIndex(int r, int c) {
        return (r-1) * 50 + c;
    }

전체 코드(84.6점)

import java.util.*;
class Solution {
    int[] parent;
    String[] table;
    List<String> result;

    public String[] solution(String[] commands) {
        parent = new int[2501];
        table = new String[2501];
        result = new ArrayList<>();
        for (int i = 1; i <= 2500; i++) {
            parent[i] = i;
        }

        for (String cmd : commands) {
            commandResolver(cmd);
        }


        String[] answer = new String[result.size()];
        int idx = 0;
        for (String str : result) {
            answer[idx] = str;
            idx++;
        }

        return answer;
    }

    private void commandResolver(String str) {
        String[] cmdArr = str.split(" ");
        String cmd = cmdArr[0];
        int len = 0;
        int r = 0;
        int c = 0;
        int r2 = 0;
        int c2 = 0;
        String val1 = "";
        String val2 = "";

        if (cmd.equals("UPDATE")) {
            len = cmdArr.length;
            if (len == 4) {
                //해당 위치에 값 기입
                r = Integer.parseInt(cmdArr[1]);
                c = Integer.parseInt(cmdArr[2]);
                val1 = cmdArr[3];
                updateRCvalue(makeParentIndex(r, c), val1);
            }
            // 모든 값 바꾸기
            if (len == 3) {
                val1 = cmdArr[1];
                val2 = cmdArr[2];
                updateChangeValue(val1, val2);
            }
            return;
        }
        r = Integer.parseInt(cmdArr[1]);
        c = Integer.parseInt(cmdArr[2]);

        if (cmd.equals("MERGE")) {
            r2 = Integer.parseInt(cmdArr[3]);
            c2 = Integer.parseInt(cmdArr[4]);
            mergeTwoRC(makeParentIndex(r, c), makeParentIndex(r2, c2));
        }
        if (cmd.equals("UNMERGE")) {
            unMerge(makeParentIndex(r, c));
        }
        if (cmd.equals("PRINT")) {
            printValue(makeParentIndex(r, c));
        }
        return;
    }

    private void updateRCvalue(int x, String val) {
        //해당 위치의 parent값과 동일한지 찾기
        table[getParent(x)] = val;
    }

    private void updateChangeValue(String val1, String val2) {
        getSameValueList(val1, val2);
    }

    private void mergeTwoRC(int x1, int x2) {

        String str;
        if (table[getParent(x1)] != null) {
            str = table[getParent(x1)];
        } else {
            str = table[getParent(x2)];
        }
        int idx = unionParent(x1, x2);
        table[idx] = str;
    }

    private void unMerge(int x) {
        String str = table[getParent(x)];
        int t = getParent(x);

        for (int i = 2500; i > 0; i--) {
            if (findParent(t, i)) {
                //초기화
                table[i] = null;
                parent[i] = i;
            }
        }
        table[x] = str;

    }

    private void printValue(int x) {
        int idx = getParent(x);
        if (table[idx] == null) {
            result.add("EMPTY");
            return;
        }
        result.add(table[idx]);
    }


    private void getSameValueList(String val, String val2) {
        for (int i = 0; i < 2500; i++) {
            if (table[i] == null) continue;
            if (table[i].equals(val)) {
                updateRCvalue(i, val2);
            }
        }
        return;
    }

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

    // 합치기
    private int unionParent(int x, int y) {
        x = getParent(x);
        y = getParent(y);
        if (x > y) parent[x] = y;
        else parent[y] = x;
        return parent[x];
    }

    // 조회
    private boolean findParent(int x, int y) {
        x = getParent(x);
        y = getParent(y);
        return x == y;
    }

    // r, c 조회
    private int[] getCoordinate(int x) {
        int r = x / 50;
        int c = x % 50;
        return new int[]{r, c};
    }

    private int makeParentIndex(int r, int c) {
        return (r-1) * 50 + c;
    }


}

그래도 14번, 15번, 19번이 실패했다.

최종풀이

원인을 보니까, merge했을 때, 병합되기 전 각 cell들의 값을 그대로 둔게 원인이 되었다.
이로인해, unmerge로 유니온파인드의 값이 초기화가 되었을때, 이전에 갖고있던 값을 그대로 소지하게됨으로, 이상한 값이 나오는 것이다.

최종코드

import java.util.*;
class Solution {
    int[] parent;
    String[] table;
    List<String> result;

    public String[] solution(String[] commands) {
        parent = new int[2501];
        table = new String[2501];
        result = new ArrayList<>();
        for (int i = 1; i <= 2500; i++) {
            parent[i] = i;
        }

        for (String cmd : commands) {
            commandResolver(cmd);
        }


        String[] answer = new String[result.size()];
        int idx = 0;
        for (String str : result) {
            answer[idx] = str;
            idx++;
        }

        return answer;
    }

    private void commandResolver(String str) {
        String[] cmdArr = str.split(" ");
        String cmd = cmdArr[0];
        int len = 0;
        int r = 0;
        int c = 0;
        int r2 = 0;
        int c2 = 0;
        String val1 = "";
        String val2 = "";

        if (cmd.equals("UPDATE")) {
            len = cmdArr.length;
            if (len == 4) {
                //해당 위치에 값 기입
                r = Integer.parseInt(cmdArr[1]);
                c = Integer.parseInt(cmdArr[2]);
                val1 = cmdArr[3];
                updateRCvalue(makeParentIndex(r, c), val1);
            }
            // 모든 값 바꾸기
            if (len == 3) {
                val1 = cmdArr[1];
                val2 = cmdArr[2];
                updateChangeValue(val1, val2);
            }
            return;
        }
        r = Integer.parseInt(cmdArr[1]);
        c = Integer.parseInt(cmdArr[2]);

        if (cmd.equals("MERGE")) {
            r2 = Integer.parseInt(cmdArr[3]);
            c2 = Integer.parseInt(cmdArr[4]);
            mergeTwoRC(makeParentIndex(r, c), makeParentIndex(r2, c2));
        }
        if (cmd.equals("UNMERGE")) {
            unMerge(makeParentIndex(r, c));
        }
        if (cmd.equals("PRINT")) {
            printValue(makeParentIndex(r, c));
        }
        return;
    }

    private void updateRCvalue(int x, String val) {
        //해당 위치의 parent값과 동일한지 찾기
        table[getParent(x)] = val;
    }

    private void updateChangeValue(String val1, String val2) {
        getSameValueList(val1, val2);
    }

    private void mergeTwoRC(int x1, int x2) {

        String str;
        if (table[getParent(x1)] != null) {
            str = table[getParent(x1)];
        } else {
            str = table[getParent(x2)];
        }
        int idx = unionParent(x1, x2);
        table[idx] = str;
    }

    private void unMerge(int x) {
        String str = table[getParent(x)];
        int t = getParent(x);

        for (int i = 2500; i > 0; i--) {
            if (findParent(t, i)) {
                //초기화
                table[i] = null;
                parent[i] = i;
            }
        }
        table[x] = str;

    }

    private void printValue(int x) {
        int idx = getParent(x);
        if (table[idx] == null) {
            result.add("EMPTY");
            return;
        }
        result.add(table[idx]);
    }


    private void getSameValueList(String val, String val2) {
        for (int i = 0; i < 2500; i++) {
            if (table[i] == null) continue;
            if (table[i].equals(val)) {
                updateRCvalue(i, val2);
            }
        }
        return;
    }

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

    // 합치기
    private int unionParent(int x, int y) {
        x = getParent(x);
        y = getParent(y);
        if (x > y) parent[x] = y;
        else parent[y] = x;
        return parent[x];
    }

    // 조회
    private boolean findParent(int x, int y) {
        x = getParent(x);
        y = getParent(y);
        return x == y;
    }

    // r, c 조회
    private int[] getCoordinate(int x) {
        int r = x / 50;
        int c = x % 50;
        return new int[]{r, c};
    }

    private int makeParentIndex(int r, int c) {
        return (r-1) * 50 + c;
    }


}

마무리

유니온파인드로 푸는 것이였지만, 조건문이나 자료구조에 대한 숙련도의 부족으로 인해 이러한 실수가 일어나느것 같다.
꾸준히 문제를 풀어가며 실수를 줄이도록 해보자

신창호

한단계씩 올라가는 개발자

이전 포스트

[코딩테스트 연습] 표 병합2

프로그래머스코딩 문제

세번째 풀이

조건 다시 확인

실패한코드(50.0점)

원인분석

전체 코드(84.6점)

최종풀이

최종코드

마무리

[코딩테스트 연습] 표 병합

0개의 댓글