알고리즘 문제 유형별로 풀어보기

September 14, 2023

문제 풀이

의상(해시)

function solution(clothes) {
  const clothesSet = {};

  clothes.forEach((cloth) => {
    clothesSet[cloth[1]] = clothesSet[cloth[1]] ? clothesSet[cloth[1]] + 1 : 1;
  });

  return Object.values(clothesSet).reduce((acc, cur) => acc * (cur + 1), 1) - 1;
}

옷 종류별로 수를 센 후, 개수 + 1을 다 곱한 후 -1 해주었다. 개수 + 1을 곱한 이유는 입지 않았을 경우의 수를 더한 것! 마지막에 -1을 함으로써 모든 종류의 의상을 입지 않았을 경우를 빼주었다.

예를 들어 모자 2 / 상의 2 경우, {2 + 1(모자를 착용하지 않은 경우)} * {2 + 1(상의를 착용하지 않은 경우)} - 1(모자 & 상의 착용하지 않음) 이렇게 계산했다.

다리를 지나는 트럭(큐)

문제링크

function solution(bridge_length, weight, truck_weights) {
  let time = 0;
  let total_weights = 0;
  let truck_index = 0;
  const bridge_trucks = [];

  while (++time) {
    if (bridge_trucks.length > 0 && bridge_trucks[0].time === time) {
      total_weights -= bridge_trucks[0].weight;
      bridge_trucks.shift();
    }

    if (total_weights + truck_weights[truck_index] <= weight) {
      total_weights += truck_weights[truck_index];
      bridge_trucks.push({
        weight: truck_weights[truck_index],
        time: time + bridge_length,
      });
      truck_index++;
    }

    if (bridge_trucks.length === 0 && truck_index === truck_weights.length)
      return time;
  }
}

문제 조건 그대로 구현했다. bridge_trucks 큐에 다리를 건너는 트럭의 정보를 담았다. 무게와 빠져나가는 시간을 기재해, 빠져나가는 시간과 현재 시간이 일치할 때 큐(bridge_trucks)와 다리에 올라가있는 전체 트럭의 무게(total_weights)에서 빼주는 식으로 구현했다.

올바른 괄호(스택)

문제링크

function solution(s) {
  let sum = 0;

  for (const bracket of s) {
    if (bracket === "(") {
      sum++;
    } else {
      if (sum === 0) return false;
      sum--;
    }
  }

  return sum > 0 ? false : true;
}

이전에는 스택을 이용해 풀었던 기억이 있는데, 배열로 구현하니 효율성 검사에서 시간초과가 발생해 +-로 변경하여 풀었다.

이중우선순위큐(힙)

문제링크

function solution(operations) {
  const queue = [];

  operations.forEach((operation) => {
    const [cmd, data] = operation.split(" ");

    if (cmd === "I") {
      queue.push(Number(data));
    } else if (cmd === "D") {
      const target = (data === "1" ? Math.max : Math.min)(...queue);
      const targetIndex = queue.indexOf(target);

      queue.splice(targetIndex, 1);
    }
  });

  return queue.length > 0 ? [Math.max(...queue), Math.min(...queue)] : [0, 0];
}

문제 설명 그대로 구현한 거라 설명할 부분이 없다..!

가장 큰 수(정렬)

문제링크

function solution(numbers) {
  const answer = numbers
    .sort((a, b) => `${b}${a}` * 1 - `${a}${b}` * 1)
    .join("");
  return answer[0] === "0" ? "0" : answer;
}

문자열로 만든 다음, 1을 곱해 숫자로 변경 후 비교해 정렬해주었다. 여담이지만 정렬할 때 -는 매번 헷갈리는 거 같다. 오름차순, 내림차순 정렬 수식 매번 헷갈려서 수식 앞 뒤 바꿔가면서 해보는듯..

피로도(완전탐색)

문제링크

function solution(k, dungeons) {
  let answer = -1;
  const isVisited = Array(dungeons.length).fill(false);

  const explore = (tired, count) => {
    answer = Math.max(answer, count);

    for (let index = 0; index < dungeons.length; index++) {
      if (isVisited[index] === false && tired >= dungeons[index][0]) {
        isVisited[index] = true;
        explore(tired - dungeons[index][1], count + 1);
        isVisited[index] = false;
      }
    }
  };

  explore(k, 0);

  return answer;
}

처음부터 하나하나 경우의 수를 다 타가면서 확인하도록 짰다. 예시의 1 -> 2 -> 3, 1 -> 3 -> 2부터 해서.. 2 -> 3 -> 1, 3 -> 2 -> 1 다 돌아볼 수 있는 방법이다.

타겟 넘버(DFS/BFS)

문제 링크

function solution(numbers, target) {
  let answer = 0;

  const checkTarget = (numbers, target, index, total) => {
    if (index === numbers.length) {
      if (total === target) {
        answer += 1;
      }
      return;
    }

    checkTarget(numbers, target, index + 1, total + numbers[index]);
    checkTarget(numbers, target, index + 1, total - numbers[index]);
  };

  checkTarget(numbers, target, 0, 0);

  return answer;
}

index를 처음부터 하나하나 돌면서 모든 경우의 수를 확인했다.

네트워크(DFS/BFS)

문제 링크

function solution(n, computers) {
  let answer = 0;
  const isVisited = Array.from(Array(n), () => false);

  const dfs = (start) => {
    isVisited[start] = true;

    for (let index = 0; index < n; index++) {
      if (isVisited[index] === false && computers[start][index]) {
        dfs(index);
      }
    }
  };

  for (let index = 0; index < n; index++) {
    if (isVisited[index] === false) {
      answer++;
      dfs(index);
    }
  }
  return answer;
}

dfs로 탐색하면서 한 뭉탱이(?)를 방문할 때마다 정답값을 1씩 더했다(answer++).

게임 맵 최단거리

문제 링크

function solution(maps) {
  let answer = 0;
  const ROW = maps.length;
  const COL = maps[0].length;
  const dx = [0, 1, 0, -1];
  const dy = [1, 0, -1, 0];
  const visit = Array.from(Array(ROW), () => Array(COL).fill(0));
  const queue = [];

  visit[0][0] = 1;
  queue.push([0, 0]);
  while (queue.length > 0) {
    const [x, y] = queue.shift();
    if (x === ROW - 1 && y === COL - 1) return visit[x][y];
    for (let k = 0; k < 4; k++) {
      const nx = x + dx[k];
      const ny = y + dy[k];
      if (nx < 0 || nx >= ROW || ny < 0 || ny >= COL) continue;
      if (visit[nx][ny] || maps[nx][ny] === 0) continue;
      visit[nx][ny] = visit[x][y] + 1;
      queue.push([nx, ny]);
    }
  }

  return -1;
}

bfs로 탐색하면서 출발 지점에서 출발하여 마지막 지점에 도달했을 경우 바로 그 지점까지 이동한 블럭 개수를 리턴하고, 마지막 지점에 도달하지 못했을 경우 -1을 리턴했다.

여행경로(DFS/BFS)

문제 링크

function solution(tickets) {
  let paths = [];
  const isVisited = Array(tickets.length + 1).fill(false);

  const dfs = (departure, path) => {
    if (tickets.length + 1 === path.length) {
      paths.push(path);
      return;
    }

    for (let index = 0; index < tickets.length; index++) {
      if (isVisited[index] === false && tickets[index][0] === departure) {
        isVisited[index] = true;
        dfs(tickets[index][1], [...path, tickets[index][1]]);
        isVisited[index] = false;
      }
    }
  };

  dfs("ICN", ["ICN"]);

  return paths.sort()[0];
}

paths에 가능한 경로를 전부 다 넣고 마지막에 정렬하여 알파벳순으로 가장 빠른 경로를 리턴했다.