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

2023. 2. 5.·☕️ 커리어 & 인터뷰 준비/코딩 테스트

📍문제 링크

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

 

1713번: 후보 추천하기

첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대

www.acmicpc.net

 

📍알고리즘 분류

- 구현

- 시뮬레이션

 

📍문제 풀이

최종 후보 풀의 크기 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 변수를 활용해 코드를 간결하게 하는 방법도 있었다..

'☕️ 커리어 & 인터뷰 준비/코딩 테스트' 카테고리의 다른 글
  • 백준 17073 < 나무 위의 빗물 > JavaScript
  • 백준 11497 < 통나무 건너뛰기 > JavaScript
  • 백준 9205 < 맥주 마시면서 걸어가기 > Python
  • 백준 1912 < 연속합 > JavaScript
지식물원
지식물원
지식이 자라는 식물원!
  • 지식물원
    지식물원
    지식물원
  • 전체
    오늘
    어제
    • 분류 전체보기 (510)
      • 🎨 프론트엔드 공부 (247)
        • JS & TS (86)
        • HTML & CSS (22)
        • React & Next (49)
        • Vue & Nuxt (22)
        • 기타 (68)
      • 🤓 기술 학습 & 공부 기록 (116)
        • Node.js (0)
        • Python (37)
        • 백엔드 (0)
        • 딥러닝 (1)
        • 컴퓨터 일반 (72)
        • 개발 인프라 (6)
      • 👨‍💻 프로젝트 경험 (6)
        • Work (0)
        • Toy (6)
      • ⚙️ 개발 팁 & 노하우 (21)
        • 프론트엔드 (6)
        • 기타 (15)
      • ☕️ 커리어 & 인터뷰 준비 (88)
        • 코딩 테스트 (88)
      • 📰 기술 트렌드 & 생각 정리 (4)
      • 📚 기타 (25)
        • 마케팅 (15)
        • 비개발서적 (10)
  • 블로그 메뉴

    • 태그
  • 링크

  • 공지사항

    • 모바일 접속 시 코드 하이라이팅 깨질 때
  • 인기 글

  • hELLO· Designed By정상우.v4.10.3
지식물원
백준 1713 < 후보 추천하기 > JavaScript
상단으로

티스토리툴바