코딩 테스트/프로그래머스

[프로그래머스] 표 병합

2023. 5. 21. 10:41
목차
  1. 📙 1. 문제
  2. 문제 설명
  3.  풀이 1
  4. 🤔 2. 느낀 점
  5. 🤩 3. 한 번 더 짚고 갈 점
  6. Union-Find 알고리즘

📙 1. 문제

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

문제 설명

 풀이 1

풀이 과정

: Union-Find알고리즘을 이용한 문제

1. cell배열과 parent 배열
cell 배열 : 51x51 크기의 2차원 배열로, 각 셀에 할당된 문자열 값을 저장

parent 배열 : 51x51 크기의 2차원 배열로, 각 셀의 부모 셀(병합이 일어난 경우 해당 셀이 속한 그룹의 대표 셀)의 좌표를 저장

2. 각 기능들을 함수화해주어, 추상화하였다.

- iterateAll(callbackFn) : 모든 셀에 대해 주어진 콜백 함수를 실행

- find(coord) : 좌표 [r,c]를 찾는

- isSameCoords([r,c],parent[r][c])

function solution(commands) {
  let answer = [];
  const cell = Array(51)
    .fill()
    .map((_) => Array(51).fill(''));
  const parent = Array(51)
    .fill()
    .map((_, i) =>
      Array(51)
        .fill()
        .map((_, j) => [i, j])
    );

  for (const commandStr of commands) {
    const [command, ...rest] = commandStr.split(' ');

    switch (command) {
      case 'UPDATE':
        if (rest.length === 3) update(rest);
        else replace(rest);
        break;
      case 'MERGE':
        merge(rest);
        break;
      case 'UNMERGE':
        unmerge(rest);
        break;
      case 'PRINT':
        answer = [...answer, print(rest)];
        break;
    }
  }

  return answer;

  function update(param) {
    const [r, c, value] = param;
    const target = find([r, c]);

    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], target)) cell[i][j] = value;
    });
  }

  function replace(param) {
    const [value1, value2] = param;

    iterateAll((i, j) => {
      if (cell[i][j] === value1) cell[i][j] = value2;
    });
  }

  function merge(param) {
    const [r1, c1, r2, c2] = param;
    if (r1 === r2 && c1 === c2) return;

    const value = cell[r1][c1] !== '' ? cell[r1][c1] : cell[r2][c2];
    const parent1 = find([r1, c1]);
    const parent2 = find([r2, c2]);

    if (!isSameCoords(parent1, parent2)) {
      parent[r2][c2] = parent1;
    }

    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], parent2)) {
        parent[i][j] = parent1;
      }
      if (isSameCoords(parent[i][j], parent1)) {
        cell[i][j] = value;
      }
    });
  }

  function unmerge(param) {
    const [r, c] = param;
    const value = cell[r][c];
    const target = find([r, c]);

    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], target)) {
        cell[i][j] = '';
        parent[i][j] = [i, j];
      }
    });

    cell[r][c] = value;
  }

  function print(param) {
    const [r, c] = param;

    return cell[r][c] === '' ? 'EMPTY' : cell[r][c];
  }

  function find(coord) {
    const [r, c] = coord;

    if (isSameCoords([r, c], parent[r][c])) {
      return [Number(r), Number(c)];
    }

    parent[r][c] = find(parent[r][c]);

    return parent[r][c];
  }

  function isSameCoords(coord1, coord2) {
    return coord1.toString() === coord2.toString();
  }

  function iterateAll(callbackFn) {
    for (let i = 0; i < 51; i++) {
      for (let j = 0; j < 51; j++) {
        callbackFn(i, j);
      }
    }
  }
}

🤔 2. 느낀 점

어렵다.

 

🤩 3. 한 번 더 짚고 갈 점

50x50의 빈 배열 : Array(50).fill().map((_)=>Array(51).fill(''))

50x50의 index로 채운 배열 : Array(50).fill().map((_,i)=>Array(50).fill().map((_,j)=>[i,j))

Union-Find 알고리즘

  • Disjoin Set : 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
  • 공통 원소가 없는, 즉 '상호 배타적'인 부분 집합들로 나눠진 원소들에 대한 자료구조
  • Unifon-Find : Disjoint Set을 표현할 때 사용하는 알고리즘
    • make-set(x) : 초기화, x를 유일한 원소로하는 새로운 집합을 만듬
    • union(x,y) : 합하기, x가 속한 집합과 y가 속한 집합을 합침
    • find(x) : 찾기, x가 속한 집합의 대표값(루트 노드 값)을 반환. x가 어떤 집합에 속해 있는지 찾는 연산

참고 : Union-Find

저작자표시 (새창열림)

'코딩 테스트 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 개인정보 수집 유효기간  (0) 2023.06.19
[프로그래머스] 수식 최대화  (0) 2023.05.26
[프로그래머스] 코딩테스트 공부  (0) 2023.05.20
[프로그래머스] 표현 가능한 이진트리  (1) 2023.05.19
[프로그래머스] 거리두기 확인하기  (0) 2023.05.14
[프로그래머스] 방금 그곡  (1) 2023.05.13
[프로그래머스] 후보키  (0) 2023.05.12
[프로그래머스] 문자열 압축  (0) 2023.05.11
  1. 📙 1. 문제
  2. 문제 설명
  3.  풀이 1
  4. 🤔 2. 느낀 점
  5. 🤩 3. 한 번 더 짚고 갈 점
  6. Union-Find 알고리즘
'코딩 테스트/프로그래머스' 카테고리의 다른 글
  • [프로그래머스] 개인정보 수집 유효기간
  • [프로그래머스] 수식 최대화
  • [프로그래머스] 코딩테스트 공부
  • [프로그래머스] 표현 가능한 이진트리
피터s
피터s
1년차 프론트엔드 개발자입니다 😣 아직 열심히 배우는 중이에요! 리액트를 하고있어요 :) - gueit214@naver.com - https://github.com/gueit214
피터s
피터의 성장기록
피터s
전체
오늘
어제
  • 분류 전체보기 (200)
    • 코딩 테스트 (25)
      • 프로그래머스 (16)
      • LeetCode (8)
      • 백준 (1)
    • 개발 독서 일지 (1)
    • 기업 분석 (4)
    • 개발 일지 (19)
      • 최신기술 도전기 (1)
      • 에러 처리 (5)
      • 개발 일지 (12)
    • 개발 일상 (36)
      • 개발 회고 (22)
      • 개발 이야기 (12)
      • 개발 서적 (1)
    • 취업 관련 지식 (11)
    • 알고리즘 (17)
    • WebProgramming (84)
      • WebProgramming (8)
      • HTML (5)
      • CSS (8)
      • JS (21)
      • React (40)

블로그 메뉴

  • About
  • 2022년 개발 성장기
  • 앞으로의 계획
  • github
  • 일상 blog

공지사항

인기 글

태그

  • LV2
  • 스터디 후기
  • 해커톤
  • Retry
  • Kakao Tech Internship
  • 개발 회고
  • 카카오
  • Union-find
  • 구름톤
  • BFS
  • KAKAO BLIND
  • 개발 is life
  • 1년 회고
  • 1일 1커밋 후기
  • lv3
  • dfs
  • 반복문
  • 구름
  • 누적합
  • 개발 일상
  • 카카오 채용연계형 인턴십
  • 함수

최근 댓글

최근 글

hELLO · Designed By 정상우.
피터s
[프로그래머스] 표 병합
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.