[프로그래머스] 81303 & 81304 & 81305 - 자바스크립트

안녕하세요. 동쪽별입니다.

최근 2022 카카오 채용연계형 인턴십에 지원했기에 작년 문제들을 풀어봤어요.

너무 어려웠습니다...

몇 문제들은 도저히 해결하지 못해 다른 사람의 문제 접근 방법을 참고했어요. 

그래서 저도 어려웠던 문제들에 대해 자바스크립트로 구현한 코드를 공유해보려 합니다.

 

---

[81303] 표 편집 

코딩테스트 연습 - 표 편집

 

Linked List 를 이용했습니다.

• 먼저 0 부터 차례대로 n-1 까지 연결하는 양방향 연결 리스트를 생성합니다.
• 그리고 명령어에 따라 생성한 연결리스트에서 이동(U, D), 삭제(C), 삽입(Z)을 수행합니다.

 

⏱ 시간복잡도 : O(n)

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

function solution(n, k, cmd) {
  const answer = [];
  const removed = [];

  let selected = null;
  let head = null;

  // Linked List 생성
  for (let row = 0; row < n; row++) {
    answer[row] = 'O';
    const node = new Node(row);

    if (!head) {
      head = node;
      continue;
    }

    head.next = node;
    node.prev = head;
    head = head.next;

    if (row === k) {
      selected = node;
    }
  }

  for (const s of cmd) {
    let [ch, count] = s.split(' ');
    count = Number(count);

    switch (ch) {
      case 'C':
        removed.push(selected);
        answer[selected.value] = 'X';

        if (selected.prev) {
          selected.prev.next = selected.next;
        }

        if (selected.next) {
          selected.next.prev = selected.prev;
          // 삭제 후 아래 행 선택
          selected = selected.next;
        } else {
          // 삭제 후 윗 행 선택
          selected = selected.prev;
        }
        break;
      case 'Z': 
        const restore = removed.pop();
        answer[restore.value] = 'O';

        if (restore.prev) {
          restore.prev.next = restore;
        }

        if (restore.next) {
          restore.next.prev = restore;
        }
        break;
      case 'D': 
        while (count--) {
          selected = selected.next;
        }
        break;
      case 'U': 
        while (count--) {
          selected = selected.prev;
        }
    }
  }

  return answer.join('');
}

 

처음에 정방향 딕셔너리, 역방향 딕셔너리를 이용하는 방법으로 접근했었습니다.

약 5시간 삽질하다가 포기하고.. 결국 다른 사람의 문제 접근 방법을 참고했어요.

참고한 방법에 따라 Linked List를 이용하니 각 명령어에 따라 로직이 딱 맞아 떨어지는 것을 보고, 아.. Linked List가 답이구나... 생각했습니다 😂

문제 해결로 Linked List를 사용한 것이 처음이라 전~혀 떠올리지 못했어요.

문제에서 빈번한 삽입, 삭제, 이동을 요구한다면  Linked List를 떠올려보면 좋을거 같아요.

 

---

[81304] 미로 탈출

코딩테스트 연습 - 미로 탈출

 

Bit Masking과 Dijkstra를 사용합니다. 

이때, 효율적인 Djkstra를 위해 Heap과 Priority Queue를 구현했습니다.

자바스크립트에는 Priority Queue를 위한 모듈이 없어서 참 슬프네요.. 파이썬이 그리웠습니다 😅

로직은 코드 주석을 통해 이해해주시기 바랍니다 🙏

만약, 코드로 이해가 안되시거나 비트 마스킹에 대해 잘 모르시는 분은 아래 영상을 보면 이해가 되실겁니다. (다만, 파이썬이라는 점..)

저도 봤어요..😆

 

 

⏱ 시간 복잡도: O(nlogn)

class Heap {
  constructor() {
    this.heap = [];
  }

  peek = () => {
    return this.heap[0];
  };

  getLeftChild = (parent) => {
    return parent * 2 + 1;
  };

  getRightChild = (parent) => {
    return parent * 2 + 2;
  };

  getParent = (child) => {
    return Math.floor((child - 1) / 2);
  };

  insert = (key, value) => {
    const node = { key, value };
    this.heap.push(node);
    this.heapifyUp();
  };

  remove = () => {
    const count = this.heap.length;
    const root = this.heap[0];

    if (count <= 0) return;

    if (count === 1) {
      this.heap = [];
    } else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    return root;
  };

  heapifyUp = () => {
    let index = this.heap.length - 1;
    const insertedNode = this.heap[index];

    while (index > 0) {
      const parent = this.getParent(index);

      if (this.heap[parent].key > insertedNode.key) {
        this.heap[index] = this.heap[parent];
        index = parent;
      } else {
        break;
      }
    }

    this.heap[index] = insertedNode;
  };

  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const root = this.heap[index];

    while (this.getLeftChild(index) < count) {
      const leftChild = this.getLeftChild(index);
      const rightChild = this.getRightChild(index);

      let minChild;

      if (
        rightChild < count &&
        this.heap[rightChild].key < this.heap[leftChild].key
      ) {
        minChild = rightChild;
      } else {
        minChild = leftChild;
      }

      if (this.heap[minChild].key <= root.key) {
        this.heap[index] = this.heap[minChild];
        index = minChild;
      } else {
        break;
      }
    }

    this.heap[index] = root;
  };
}

class PriorityQueue extends Heap {
  constructor() {
    super();
  }

  enqueue = (priority, value) => {
    this.insert(priority, value);
  };

  dequeue = () => {
    return this.remove();
  };

  isEmpty = () => {
    return this.heap.length <= 0;
  };
}

function dijkstra(n, graph, start, end, traps) {
  const pq = new PriorityQueue();
  const visited = Array(n + 1).fill(0).map((_) => []);

  // 비트 마스크 초기화
  // 각 비트는 함정의 on/off 여부를 나타냄 (1 = 함정 on, 0 = 함정 off)
  for (let i = 1; i < n + 1; i++) {
    for (let j = 0; j < 1 << traps.length; j++) {
      visited[i][j] = 0;
    }
  }

  // (누적 시간, [방 번호, 함정 상태]) 형태로 우선순위 큐에 삽입
  pq.enqueue(0, [start, 0]);

  while (!pq.isEmpty()) {
    const curr = pq.dequeue();
    const w = curr.key; // 누적 시간
    const u = curr.value[0]; // 방 번호
    let state = curr.value[1]; // 각 함정의 on/off 여부

    // 도착
    if (u === end) {
      return w;
    }

    // '방 번호'와, '함정의 상태' 두가지 요소로 방문 여부를 판단
    if (visited[u][state]) {
      continue;
    }

    visited[u][state] = true;

    let currTrapped = false;
    const trapped = new Map();

    for (let i = 0; i < traps.length; i++) {
      const bit = 1 << i;
      // 해당 비트의 함정 on일 경우
      if (state & bit) {
        if (traps[i] === u) {
          // 함정 재방문 - 해당 비트를 함정 off로 변경
          state = state & ~bit;
        } else {
          // 현재 on 되어있는 함정들 저장
          trapped.set(traps[i], true);
        }
      } else {
        if (traps[i] === u) {
          // 함정 첫방문 - 해당 비트를 함정 on으로 변경
          state = state | bit;
          // 현재 방의 함정 on
          currTrapped = true;
          // 현재 on 되어있는 함정들 저장
          trapped.set(traps[i], true);
        }
      }
    }

    for (let v = 1; v < n + 1; v++) {
      if (v === u) {
        continue;
      }

      // 다음 이동할 방이 on되어 있는 함정인지 확인
      const nextTrapped = trapped.has(v) ? true : false;

      if (currTrapped === nextTrapped) {
        // 현재 방과 다음 방 모두 함정이거나, 함정이 아닐 경우 - 정방향
        if (graph[u][v] !== Infinity) {
          pq.enqueue(w + graph[u][v], [v, state]);
        }
      } else {
        // 현재 방과 다음 방 중 하나라도 함정일 경우 - 역방향
        // 역방향은 row와 col을 반대로
        if (graph[v][u] !== Infinity) {
          pq.enqueue(w + graph[v][u], [v, state]);
        }
      }
    }
  }

  return Infinity;
}

function solution(n, start, end, roads, traps) {
  // 인접 행렬 그래프 생성
  const graph = Array(n + 1).fill(0)
    .map((_) => Array(n + 1).fill(Infinity));

  roads.forEach(([v1, v2, w]) => {
    // 두 방 사이 연결된 같은 방향 길 중 최소 시간 길 선택
    graph[v1][v2] = Math.min(graph[v1][v2], w);
  });

  return dijkstra(n, graph, start, end, traps);
}

 

정말 미친 문제였습니다.. 

처음에는 비트마스킹을 사용하지 않고(사용해야 되는지도 몰랐어요..), 함정에 대한 정보를 배열에 저장하는 방법으로 문제를 해결하려 했는데, 자꾸 7번만 틀렸습니다.

아무리 애를 써도 7번을 해결할 수 없었고, 결국 다른 사람의 코드를 보며 비트 마스킹에 대해 알게 되어 이를 적용해 해결했습니다.

역대급으로 힘들었던 것 같네요.

 

---

[81305] 시험장 나누기

코딩테스트 연습 - 시험장 나누기

 

Parametric Search와 Postorder Traversal, Dynamic Programming을 수행합니다.

이진 탐색으로 limit(mid) 값을 결정하여, 각 그룹의 인원수 합이 limit 이하가 되도록 하는 방법입니다.

• 주어진 이진트리를 후위 순회(Postorder Traversal)합니다.
• 순회를 하며 각 노드 마다 [현재까지의 그룹 인원수 합, 현재까지의 그룹 수] 를 저장합니다. → DP
• 자식의 정보를 바탕으로 현재 노드를 어떻게 그룹 지을지 결정합니다.
  • 만약 두 자식과 현재 노드의 인원 수 합이 limit 이하라면, 현재 노드도 그룹에 포함시킵니다.
  • 만약 자식 하나만 그룹을 지을 수 있다면, 인원 수가 더 적은 자식과 그룹을 짓습니다.
  • 어떤 자식과도 그룹을 지을 수 없다면, 현재 노드가 속한 새 그룹을 생성합니다.

• 순회를 마친 후, 루트 노드에 대해 저장한 그룹의 수(limit을 넘지 않는 한에서 만들어진 총 그룹의 수)를 리턴합니다. 
• 리턴된 값이 k 보다 작거나 같으면 right를 업데이트, 그렇지 않으면 left를 업데이트 합니다. → 이진 탐색 
• 다시 mid를 limit으로 두고, 트리 순회를 실시합니다.
• left가 right보다 커질 때까지 이를 반복합니다.

 

⏱ 시간복잡도: O(nlogn)

function solution(k, num, links) {
  const getPostorder = () => {
    const order = [];
    const stack = [root];
    const visited = Array(N).fill(false);

    outer: while (stack.length) {
      const node = stack[stack.length - 1];
      for (const child of links[node]) {
        if (child !== -1 && !visited[child]) {
          stack.push(child);
          visited[child] = true;
          continue outer;
        }
      }
      order.push(stack.pop());
    }
    return order;
  }

  const divideRoom = (limit) => {
    postorder.forEach(node => {
      const [leftChild, rightChild] = links[node];

      // 자식 노드 0개
      if (leftChild + rightChild === -2) {
        dp[node][0] = num[node];
        return;
      }
      
      // 자식 노드 1개
      if (leftChild === -1 || rightChild === -1) {
        const child = leftChild === -1 ? rightChild : leftChild;
        // - 자식과 한 그룹에 속할 수 있는 경우
        if (limit >= num[node] + dp[child][0]) {
          dp[node][0] = num[node] + dp[child][0];
          dp[node][1] = dp[child][1];
        } 
        // - 자식과 그룹이 될 수 없는 경우
        else { 
          dp[node][0] = num[node];
          dp[node][1] = dp[child][1] + 1;
        }
        return;
      }

      // 자식 노드 2개
      // - 자식 둘과 한 그룹에 속할 수 있는 경우
      if (limit >= num[node] + dp[leftChild][0] + dp[rightChild][0]) {
        dp[node][0] = num[node] + dp[leftChild][0] + dp[rightChild][0];
        dp[node][1] = dp[leftChild][1] + dp[rightChild][1] - 1;
      }
      // - 자식 하나만 한 그룹에 속할 수 있는 경우 (둘 중 작은 자식 선택)
      else if (limit >= num[node] + Math.min(dp[leftChild][0], dp[rightChild][0])) {
        dp[node][0] = num[node] + Math.min(dp[leftChild][0], dp[rightChild][0]);
        dp[node][1] = dp[leftChild][1] + dp[rightChild][1];
      }
      // - 자식 둘과 모두 그룹이 될 수 없는 경우
      else {
        dp[node][0] = num[node];
        dp[node][1] = dp[leftChild][1] + dp[rightChild][1] + 1;
      }
    })

    return dp[root][1];
  }

  const N = num.length;
  const indegree = Array(N).fill(0);
  
  links.forEach(([leftChild, rightChild]) => {
    leftChild !== -1 && indegree[leftChild]++;
    rightChild !== -1 && indegree[rightChild]++;
  });

  const root = indegree.indexOf(0);
  const postorder = getPostorder();
  const dp = Array(N).fill(0).map((_) => [0, 1]);

  let left = Math.max(...num);
  let right = num.reduce((a, b) => a + b);

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (divideRoom(mid) <= k) right = mid - 1;
    else left = mid + 1;
  }

  return left;
}

 

처음엔 우선순위 큐를 이용한 방법으로 접근했지만.. 역시나 실패했습니다.

결국 다른 사람의 접근 방법을 참고하여 이진 탐색, 후위 순회, DP를 사용하여 해결할 수 있었습니다.

개인적으로 이진 탐색이 가장 어려운거 같아요 🤔

이진 탐색을 사용하는 아이디어는 떠올리기가 정말 힘듭니다..

 

 

 

.

.

.

 

 

 

'[81304] 미로 탐색' 문제는 방법만 보고서는 잘 모르겠더라구요.

아마 비트 마스킹을 잘 모른 탓이었던 것 같습니다.

그래서 코드를 보며 이해하려고 자바스크립트 코드를 구글링 해보니 없더라구요..

결국 파이썬 코드를 보며 이해하고 자바스크립트로 구현했습니다.

자바스크립트로 구현한 제 코드들이 저처럼 문제 해결에 대한 방법을 찾으려는 누군가에게 도움이 되었으면 좋겠네요.