후보 추천하기

문제

언어

  • JavaScript

순서도

  1. 학생의 추천수와 게시된 시간을 기록하는 2 차원 배열 생성
    • [[추천 수, 게시된 시간], [추천 수, 게시된 시간], …]
  2. 전체 학생의 추천 결과를 하나씩 순회하며, 최종적으로 게시되어 있는 후보의 번호 나열
    • 이미 게시된 학생이면, 추천수만 증가
    • 게시되지 않은 학생이면, 사진틀이 비어있는지 확인 후에 게시하기
  3. 최종적으로 게시된 학생들의 번호를 오름차순으로 정렬 후 출력

문제 풀이 step 1

  • 본 문제는 시뮬레이션 형식의 문제로, 문제에서 주어진 조건대로 로직을 짜는 문제입니다.
  • 학생회장 후보를 정하려고 합니다.
    • 추천받은 학생의 사진을 게시할 수 있는 사진틀이 N 개 있습니다.
    • 처음에는 N 개의 사진틀이 모두 비어있습니다.
    • 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 합니다.
    • 비어있는 사진틀이 없다면, 현재까지 추천받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시합니다.
    • 현재까지 추천받은 횟수가 가장 적은 학생이 여러명이라면 그 중에서 게시된지 가장 오래된 사진을 삭제합니다.
    • 현재 사진이 게시된 학생이 추천을 받으면, 추천받은 횟수만 증가시킵니다.
    • 사진틀에 게시된 사진이 삭제되면, 해당 학생이 추천받은 횟수는 0 으로 바뀝니다.
  • 위와 같은 규칙이 있을 때, 사진틀에 사진이 게재된 최종 후보의 학생 번호를 구하는 문제입니다.

문제 풀이 step 2

  • 총 학생이 100 명이기 때문에 100 명의 추천 정보를 담기 위한 배열을 생성합니다.
    • 배열의 형태는 [[추천 수, 게시된 시간], [추천 수, 게시된 시간], …] 과 같습니다.
  • 추천 정보를 하나씩 순회하며,
    • 이미 사진틀에 사진이 게재된 학생일 경우, 추천 수만 늘려줍니다.
    • 게재된 학생이 아니라면, 우선 사진틀에 빈 공간이 있는지 확인합니다.
      • 빈공간이 없다면, 추천수가 가장 적고 게재된지 가장 오래된 학생의 사진을 제거합니다.
      • 빈공간이 있다면, 게재해주면 되겠습니다.
  • 학생들의 추천 정보를 담은 배열을 순회하며, 최종적으로 게재된 학생 번호를 모으고, 오름차순으로 졍렬한 결과를 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 저의 경우는 CountSort 기법을 기반으로 풀었습니다. 어차피 학생의 수가 100 명 밖에 안되기 때문에 이런 선택을 했습니다.
    • 더 직관적인 자료구조를 만들어서 푸는 방법도 있겠습니다.
  • 정말 간단하고, 정말 당연한 건데 게재된 사진을 제거 후에 사진을 게재해야 하는데, 새로운 학생의 사진을 게재하고 사진을 제거하는 “순서가 잘못된 로직”으로 인해서 많은 시행착오를 겪었습니다.
    • 새로 게재된 사진의 시간이 가장 최근이기 때문에 삭제되지 않을 것이라는 안일한 생각을 했습니다.
    • 기존에 게재된 사진들의 추천수가 모두 2 이상이라면 새로 추가되는 사진은 삭제될 수 밖에 없는 구조였습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const deleteStudent = (students) => {
	let min = 10000;
	let deleted = 0;

	for (let i = 1; i < 101; i++) {
		// 게시되지 않은 학생은 skip
		if (students[i][0] === 0) continue;

		// 최솟값 찾고,
		if (students[i][0] < min) {
			min = students[i][0];
			deleted = i;
		}

		// 최솟값이 동일하다면, 더 먼저 게시된 학생으로 선택
		if (students[i][0] === min) {
			if (students[i][1] < students[deleted][1]) {
				deleted = i;
			}
		}
	}

	// 사진 제거
	students[deleted] = [0, 0];
};

const solution = (input) => {
	const n = Number(input[0]);
	const k = Number(input[1]);
	const nums = input[2].split(" ").map(Number);

	// [추천 수, 게시된 시간]
	const students = Array.from({length: 101}, () => [0, 0]);

	let cnt = 0;
	for (let i = 0; i < k; i++) {
		const num = nums[i];

		// 이미 게시된 학생이라면 추천수 증가
		if (students[num][0] > 0) {
			students[num][0] += 1;
			continue;
		}

		// 사진틀이 모두 꽉 차있다면, 게시된 사진 삭제
		if (cnt === n) {
			deleteStudent(students);
			cnt -= 1;
		}

		// 새로운 학생의 사진 게시
		students[num][0] += 1;
		students[num][1] = i;
		cnt += 1;
	}

	// 최종적으로 게시된 학샏들의 번호 찾기
	const res = [];
	for (let i = 1; i < 101; i++) {
		if (students[i][0] === 0) continue;

		res.push(i);
	}

	return res.join(" ");
};

console.log(solution(input));