[10주차_목요일] 표 병합

[yeahdy]

• 사이트 : 프로그래머스(PG)
• 문제: 표 병합
• 번호: 150366
• 레벨: 3

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[yeongleej]

🤔 시간복잡도 고려사항

• 표의 크기 : 50 * 50
• commands의 길이 ≤ 1,000

=> 최대 시간복잡도: 각 command당 5050의 탐색이 일어남 -> O(50 50 * 1000) 약 2,500,000 => 완전탐색 가능

💡 풀이 아이디어

• g[r][c] : (r, c)의 값을 기록

• 각 셀과 연결된 셀들을 기록하기 위해 각 셀에대한 link 리스트 설정

  • List<Integer>[] link; : link[i] 는 i번째 셀과 연결된 셀들의 리스트 -> BFS 탐색을 이용하기 위함
  • 이때 표는 2차원이므로 1차원으로 바꿔서 기록
    • 예) (r, c) -> r*N + c

• linking(r, c, v, isUnmerge) : (r, c)와 연결된 셀들의 값을 모두 v로 바꿈

  • BFS 탐색으로 연결된 셀들 값 변경

  • isUnmerge가 true이면 (r,c)와 연결된 셀들의 연결리스트를 초기화해야 함

    public static void linking(int r, int c, String v, boolean isUnmerge) {
    Queue<Integer> q = new LinkedList<>();
    boolean[][] visited = new boolean[N][N];
    
    q.add(r*N + c);
    visited[r][c] = true;
    
    while(!q.isEmpty()) {
        int now = q.poll();
        int x = now / N;
        int y = now % N;
        g[x][y] = v;
        for(int next: link[now]) {
            int nx = next / N;
            int ny = next % N;
            if(visited[nx][ny]) continue;
    
            visited[nx][ny] = true;
            q.add(next);
        }
        if(isUnmerge) link[now] = new ArrayList<>();
    }
    }

• UPDATE r c value

  • g[r][c]값을 변경하고 (r, c)와 연결된 셀들 linking() 실행

• UPDATE value1, value2

  • 모든 셀을 반복해서 value1과 같은 셀의 값을 value2로 변경 (linking 과정 필요 X)

• MERGE r1 c1 r2 c2

  • 문제의 조건에 맞게 (r1, c1)과 (r2, c2)를 병합하고 연결된 셀들 linking() 실행

• UNMERGE r c

  • (r, c)와 연결된 셀들을 지우는 linking() 실행
  • (r, c)에는 원래값 대입

• PRINT r c : 출력 진행

BFS로 풀었는데, Union-FInd 문제였네요,,!! ㅎㅎ

[baexxbin]

🤔 시간복잡도 고려사항

• 표의 크기 : 50 * 50
• commands의 길이 ≤ 1,000
• 완전탐색 가능: 50501000

💡 풀이 아이디어

• 유니온 파인드 이용
  • 셀을 병합하고, 병합된 셀엔 대표 값들을 가짐(유니온 파인드 개념 활용 가능)
• 문자열 파싱해서 명령어 별로 함수 나누기
• merge()
  • 각 셀의 부모 인덱스 구한 후, 대표 셀 값 설정해서 union()진행

    if (p1 != p2) {
          String val = board[p1] != null ? board[p1] : board[p2];
          union(p1, p2, val);
      }

• updateOne()
  • 선택한 셀의 부모 값을 찾은 후, 부모 값 업데이트
• updateAll()
  • 배열을 순회하면서 바꿀 target 값이면 변경
  • 이때 빈 값엔 null이 들어있기에 Objects.equals() 활용

• unmerge()

  • for문 돌면서 바로 부모 값 변경하면, 최종 루트값까지 가는 경로가 끊기기에 candi리스트에 담아줬다가 삭제

    private static void unmerge(String[] cmd) {
    int r = Integer.parseInt(cmd[1])-1;
    int c = Integer.parseInt(cmd[2])-1;
    
    int idx = r*50+c;           // 선택된 r,c 셀 인덱스
    int p = find(idx);           // 해당 셀의 부모 인덱스 (병합 대표)
    String val = board[p];      // 부모 인덱스의 값 (병합 대표 값)
    
    // 병합 해제될 셀 추적 리스트
    List<Integer> candi = new ArrayList<>();
    
    // 병합해제할 셀 후보로 담기
    for (int i = 0; i < N; i++) {
        if (find(i) == p) {
            candi.add(i);
        }
    }
    
    // 병합해제할 셀 값 복원
    for (Integer cell : candi){
        parents[cell] = cell;
        board[cell] = null;
    }
    
    // 타겟 병합해제 셀은 원래 값 유지
    board[idx] = val;
    }

• print()
  • 셀 값에 해당하는 값 출력

14-22번까지 계속 틀려서 문제가 뭘까 엄청 고민했었는데 인덱스 문제였습니다... 0인덱스로 설정을 안해줘서(-1)... 인덱스 놓치지 않기!! 문자열도 다루고 유니온 파인드도 연습할 수 있어서 좋은 문제였던것 같습니당

[icegosimperson]

🤔 시간복잡도 고려사항

표 크기 50*50, 문자열 길이 <= 1000 : 구현 가능

💡 풀이 아이디어

• Union-find, 입력 받는 명령어를 switch문으로 구분

1) case UPDATE

• hasMoreTokens()를 사용해서 UPDATE v1 v2 value, UPDATE v1, v2 구분

  case "UPDATE" : // UPDATE 추출
  String v1 = st.nextToken(); // v1 추출
  String v2 = st.nextToken(); // v2 추출
  
  if(st.hasMoreTokens()){ // 남아있는 토큰이 있는 경우 (UPDATE v1 v2 value)
      String value = st.nextToken(); // value 추출
      r = Integer.parseInt(v1) - 1;
      c = Integer.parseInt(v2) - 1;
      values[find(r * 50 + c)] = value;
      }
  
  else{ // UPDATE v1 v2
      for(int j = 0; j < n; j++){
      if(values[find(j)] != null && values[find(j)].equals(v1)){
          values[find(j)] = v2;
          }
      }
  }
  break;

  2) case MERGE

• 두 칸 병합 -> 하나 만 대표 칸이 됨 -> 그 값 공유

• 한 칸만 값이 있는 경우 : 병합 후 그 값 유지

  
  case "MERGE":
  int r1 = Integer.parseInt(st.nextToken()) - 1;
  int c1 = Integer.parseInt(st.nextToken()) - 1;
  int r2 = Integer.parseInt(st.nextToken()) - 1;
  int c2 = Integer.parseInt(st.nextToken()) - 1;
  
  int num1 = r1 * 50 + c1;
  int num2 = r2 * 50 + c2;
  
  // 값이 없는 칸이 대표가 되지 않게 처리
  if (values[find(num1)] == null && values[find(num2)] != null) {
      int temp = num1;
      num1 = num2;
      num2 = temp;
  }
  
  union(num1, num2); // 두 칸 병합
  break;

3) case `UNMERGE` : 병합된 칸 초기화
```java
case "UNMERGE":
    r = Integer.parseInt(st.nextToken()) - 1;
    c = Integer.parseInt(st.nextToken()) - 1;

    int g = find(r * 50 + c);  // 대표 칸 찾기
    v = values[g];            // 대표 칸의 값 저장

    // 모든 셀에 대해 경로 압축 수행
    for (int j = 0; j < n; j++) {
        find(j);
    }

    for (int j = 0; j < n; j++) {
        if (find(j) == g) {      // 동일한 대표 칸을 가진 경우 초기화
            grp[j] = j;          // 병합된 셀을 개별 셀로 분리

            if (j == r * 50 + c) {
                values[j] = v;   // 지정된 칸의 값 유지
            } else {
                values[j] = null; // 나머지 칸 초기화
            }
        }
    }
    break;

4) case PRINT : list-> String[] 출력

case "PRINT":
    r = Integer.parseInt(st.nextToken()) - 1;
    c = Integer.parseInt(st.nextToken()) - 1;

    v = values[find(r * 50 + c)]; // 대표 칸의 값 가져오기

    if (v == null) {
        answers.add("EMPTY");    // 값이 없는 경우 "EMPTY" 추가
    } else {
        answers.add(v);          // 값이 있으면 추가
    }
    break;

처음에 단순 구현 문제인줄 알고 풀었었는데 테케 틀려서 찾아보니까 유니온 파인드로도 풀 수 있는 문제더라고요..! 문자열 입출력, 유니온 파인드 복습 할 수 있어서 좋았습니다

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 구현 + union-find
• 시간복잡도: 표의 크기는 50 × 50 1 ≤ commands의 길이 ≤ 1,000 union-find 으로 풀 경우 O(N) > 2500 완전탐색도 가능할 것 같음

💡 풀이 아이디어

• 2차원 배열을 1차원 배열로 만들어서 union-find 탐색 진행
  • 1차원 배열에서 인덱스 찾기

    // 0부터 시작할 경우
    (r-1)*columns.length + c-1 

• UPDATE MERGE UNMERGE PRINT 별로 나눠서 함수 구현
• UPDATE
  • find를 통해 부모 인덱스가 보는 표의 값을 찾아서 update
  • merge 전 초기값은 자기 자신이 부모이므로 표에서 다이렉트로 본인 자리로 값이 갱신
  • merge 후 자기 자신이 부모가 아닐 수도 있기 때문에 표에서 부모 인덱스의 자리 값이 갱신

• MERGE

  • union-find 탐색을 통해 두 셀의 부모를 찾아서 r1,c1 을 기준으로 합치기

    public void union(int num1, int num2){
    num1 = find(num1);
    num2 = find(num2);
    
    if(num1 == num2){   //이미 병합된 경우
        return;
    }
    table[num1] = table[num1].isBlank()? table[num2] : table[num1];
    parents[num2] = num1;
    table[num2] = null;
    }

• UNMERGE

  • find를 통해 주어진 셀의 부모인덱스를 찾고, 해당 부모인덱스를 가지고 있는 다른 셀들을 찾아서 초기화 진행

  • 초기화 하기 전 find 를 통해 부모인덱스 갱신하기

    public void unmerge(int r, int c){
    for(int i=0; i<MAX; i++){
        find(i);
    }
    
    int index = getIndex(r, c);     //표 인덱스
    int parent = parents[index];    //병합된 부모찾기
    String value = table[parent];   //부모의 value
    
    for(int i=0; i<table.length; i++){
        if(parents[i] == parent){
            parents[i] = i;     //부모에서 벗어나기
            table[i] = "";    //병합 해제 후 셀 초기화
        }
    }
    table[index] = value;
    }

계속 테케 11~16 , 18번에서만 런타임에러 발생하는데, String 배열 초기값을 "" 으로 바꿔보고(NPE), 배열크기를 넉넉히(ArrayIndexOutOfBoundsException) 해봤는데도 런타임에러가 발생하네요.. 질문하기에 있는 반례 테케 다 넣어서 실행해보면 통과하는데 도대체.. 어떤게 문제인지 모르겠어요😫😭 토요일날 같이 디버깅해주실 스터디원 분들....

[Jewan1120]

🤔 시간복잡도 고려사항

• 표의 크기는 50 × 50으로 고정 → 따로 고려하지 않았음

💡 풀이 아이디어

• 그룹을 만드는 문제 → union-find
• update시에는 명령어에 따라서 updateCell와 updateArea로 나누어 작성
• updateCell(): 바꾸려는 cell과 동일한 부모를 가지는 모든 cell의 값 변경
• updateArea(): 바꾸려는 문자열과 동일한 문자열을 가지는 모든 cell의 값 변경
• merge(): 두 셀을 union을 하고 해당 그룹의 부모를 가진 모든 cell의 값을 특정 값으로 변경
• unmerge(): 해당 셀의 부모를 찾은 뒤 해당 부모를 가지는 모든 cell의 값을 빈 값으로 변경 후 연결 관계 끊어줌
• print(): 해당 셀 참조해서 반환

  빡센 구현...

[KodaHye]

🤔 시간복잡도 고려사항

• 50 ⨉ 50 크기의 표에서 구현

💡 풀이 아이디어

• 구현으로 풀이함
• String[][] table: 원소 값을 가지고 있는 배열
• int[][] markGroupNum: 각 좌표마다 그룹 번호를 메겨줌
  • 초기 값: r * 51 + c
• HashMap<Integer, HashSet<Point>> hashMap: 그룹 번호에 대해 어떤 지점들이 있는지 저장
  • 초기에는 key: r * 51 + c에 대해 r, c 지점이 들어있음
• update()
  • 바꾸려는 지점의 GroupNum을 알아내서 그 그룹에 있는 지점의 값들 다 바꿔주기
• merge()
  • 문제 조건에 나온 대로 부모가 될 원소와 자식이 될 원소 지정한 뒤, table, markGroupNum, hashMap 정보 업데이트 해주기
• unmerge()
  • unmerge하려는 지점의 GroupNum을 알아내고 그 그룹에 있는 모든 지정의 table 정보 null로 바꿔주고, groupNum에 r * 51 + c 값 넣어주고, hashMap 정보 업데이트해주기

~최대한 풀어보려고 했는데,,, 1, 10, 13, 14, 16에서 실패하네요!!!!!!!!!!!,,,, 근데 어디서 잘못된지는 잘 모르겠습니다 ㅠㅠ,,,, 리뷰 전까지 한 번 더 봐보고,,,, 안되면,,, 저도,,,, 코드상 오류 한 번만 봐주시면 감사하겠습니다1!!!~

해결완료!!! unmerge()과정에서 오류가 있었네요!!

원래 코드

static void unmerge(int r, int c) {
  int key = markGroupNum[r][c];

  ArrayList<Point> removeSet = new ArrayList<Point>();
  for(Point p: hashMap.get(key)) {
      int nextKey = p.r * 51 + p.c;
      markGroupNum[p.r][p.c] = nextKey;
      table[p.r][p.c] = null;

      removeSet.add(p);
      hashMap.get(nextKey).add(p);
  }

  hashMap.get(key).removeAll(removeSet);
}

수정코드

static void unmerge(int r, int c) {
    int key = markGroupNum[r][c];
    String value = table[r][c];

    hashMap.get(key).clear();

    for(int rr = 1; rr < table.length; rr++) {
        for(int cc = 1; cc < table[0].length; cc++) {
            if(markGroupNum[rr][cc] == key) {
                int realKey = rr * 51 + cc;
                table[rr][cc] = null;
                markGroupNum[rr][cc] = realKey;
                hashMap.get(realKey).add(new Point(rr, cc));
            }
        }
    }
    table[r][c] = value;
}

처음 했던 방법은 key 값이 r * 51 + c인 경우에만 성립되는 코드였고, 제가 구현을 이상하게 했네요!!!! 문제 해결도 했으니,,, 편히 자러 갑니다,,,