백준 1713 < 후보 추천하기 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/1713

1713번: 후보 추천하기

 

📍알고리즘 분류

- 구현

- 시뮬레이션

 

📍문제 풀이

최종 후보 풀의 크기 N과 자연수로 이루어진 수열 data을 입력받는다

- data를 순회하며 후보 N의 크기 이내에서 추천수가 높은 순으로 최종 후보를 가린다

 

문제를 풀며 우선순위 큐로 해결할 수 있겠다 생각이 들었다. 그 이유는...

- 힙 구조를 사용하면 배열보다 시간 복잡도가 빠름 (단 메모리를 더 많이 쓸 수 있음)

- 큐가 업데이트될 때마다 추천수가 낮은 학생을 자동으로 root에 배치하여 꺼내기 쉬움

 

그런데 알고리즘 분류에 구현이 있길래 그냥 배열을 이용한 쌩 구현으로 풀어보았다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
let list = [];

// 리스트에 특정 학생넘버가 있는지 검사하는 함수
const isIn = (arr, num) => {
  // 처음에 forEach 썼는데 이상하게 잘 안되서 for of 문으로 바꾸니까 잘 됨
  for (let obj of arr) {
    if (obj.num === num) return true;
  }
  return false;
};

// 특정 학생 넘버를 받아 추천수 증가시키는 함수
const setLikes = (arr, num) => {
  return arr.map((obj) => {
    if (obj.num === num) obj.likes++;
  });
};

// 추천 수가 제일 낮은 학생을 제거
const getdeletedArr = (arr) => {
  let min = Number.MAX_SAFE_INTEGER;
  let targetNum = 0;
  arr.forEach((obj) => {
    min = Math.min(min, obj.likes);
  });
  // 추천 수가 같은 학생이 여러 명이더라도 맨 먼저 추가된 학생을 제거 대상으로 삼음
  for (let obj of list) {
    if (obj.likes === min) {
      targetNum = obj.num;
      break;
    }
  }
  return arr.filter((obj) => obj.num !== targetNum);
};

// 객체가 원소인 배열에서 학생 넘버 꺼내주는 함수
const solution = (list) => {
  const answer = [];
  for (let obj of list) {
    answer.push(obj.num);
  }
  return answer;
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const size = +input[0];
  const data = input[2].split(" ").map(Number);

  for (let el of data) {
    // 큐의 사이즈에 아직 여유가 있을떄
    if (list.length < size) {
      // 입력받은 학생 넘버가 list에 없으면 추가
      if (!isIn(list, el)) {
        list.push({ num: el, likes: 1 });
        // list에 있으면 추천수만 증가
      } else {
        setLikes(list, el);
      }
      // 큐의 사이즈에 여유가 없을 때는?
    } else {
      // 입력받은 학생 넘버가 list에 없으면 젤 낮은거 지우고 추가
      if (!isIn(list, el)) {
        list = getdeletedArr(list);
        list.push({ num: el, likes: 1 });
      } else {
        setLikes(list, el);
      }
    }
  }
  console.log(
    solution(list)
      .sort((a, b) => a - b)
      .join(" "),
  );
});

 

📍리뷰

- 다른 풀이를 보니 굳이 우선순위 큐를 쓰지 않아도 toggle 변수를 활용해 코드를 간결하게 하는 방법도 있었다..