[연습문제] 18. 80 ~ 82 해시

in 코딩테스트 on 연습문제




자료구조때 공부한 문제들 다시 복습하면서 완전히 익숙해지기! 그때는 엄청 어려웠는데 이제는 수월하다….😳


80. 출석 체크 (딕셔너리)

연말이 다가와 학생들에게 개근상을 주려고 한다.
학생 별 1학기 개근 현황과 2학기 개근 현황을 파악하고 이써, 이 정보를 바탕으로 학생 별 올해 1년 동안 개근을 했는지 판단하는 프로그램을 제작하시오.
개근상은 A 학생이 1학기와 2학기 모두 출석했을 경우에만 수여한다.
입력은 1학기 개근한 학생, 2학기 개근한 학생 정보가 배열로 주어지며, 1년 전체 개근한 학생은 1학기 개근한 학생 순으로 정렬하여 배열 형태로 반환한다.

function Dictionary(items = {}) {
  this.items = items;
}

Dictionary.prototype.set = function (key) {
  this.items[key] = true;
};

Dictionary.prototype.has = function (key) {
  return this.items.hasOwnProperty(key);
};

function answer(class_1, class_2) {
  let result = [];
  // 구현
  let dict = new Dictionary();
  for (let i = 0; i < class_2.length; i++) {
    dict.set(class_2[i]);
  }

  for (let i = 0; i < class_1.length; i++) {
    if (dict.has(class_1[i])) result.push(class_1[i]);
  }
  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  [
    ["Kail", "Oliber", "Naomi"],
    ["Oliver", "Naomi", "Maya"],
  ],
  [
    ["Roxy", "Olga", "Kara", "Nana"],
    ["Oliver", "Roxy", "Kara", "Nana", "May"],
  ],
  [
    ["Roxy", "Ravi", "Nana", "Rei", "Karis", "Mana", "Naomi"],
    ["Olga", "Nana", "Rei", "Oliver", "Kali", "Rei", "Kara"],
  ],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i][0], input[i][1]));
}

// #1[ 'Naomi' ]
// #2[ 'Roxy', 'Kara', 'Nana' ]
// #3[ 'Nana', 'Rei' ]



81. 숫자 카드

카드 게임을 하기 위해 -10 ~ 10 사이의 숫자 카드를 N장 뽑았다.
이 때 M개 수가 갖는 숫자 카드가 몇 개 있는지 계산해주는 프로그램을 작성하시오.
숫자 카드 범위는 -10 <= 카드 <= 10 이며, N 과 M의 범위는 3 <= N, M <= 20 이다.
입력은 숫자 카드 범위를 만족하는 N과 M 배열이 순차적으로 들어오며, M 숫자 카드를 몇 개 갖고 있는지를 순차적으로 배열이 기록하며 반환한다.

const HASH_SIZE = 21;

function HashTable() {
  this.table = new Array(HASH_SIZE);
}

HashTable.prototype.hashCode = function (key) {
  return (key + 10) % HASH_SIZE; // -10 ~ 10 > 0 ~ 20
};

HashTable.prototype.put = function (key) {
  let index = this.hashCode(key);
  if (this.table[index] === undefined) {
    this.table[index] = 0;
  }
  this.table[index]++;
};

HashTable.prototype.get = function (key) {
  return this.table[this.hashCode(key)] === undefined
    ? 0
    : this.table[this.hashCode(key)];
};

function answer(card, select) {
  let result = [];
  // 구현
  let hash = new HashTable();
  for (let i = 0; i < card.length; i++) {
    hash.put(card[i]);
  }
  for (let i = 0; i < select.length; i++) {
    result.push(hash.get(select[i]));
  }
  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  [
    [-6, -1, 6, 1, 1],
    [-2, 1, 3],
  ],
  [
    [7, 4, 3, 10, 10, 10, -10, -10, 7, 3],
    [10, 9, -5, 4, 6, -10],
  ],
  [
    [5, -3, -7, 10, -3, 4, 8, 4, -3, 3, 8, -2, -9, -8, -1],
    [4, 5, 1, 10, -2, -3, 3, -8],
  ],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i][0], input[i][1]));
}

// #1[ 0, 2, 0 ]
// #2[ 3, 0, 0, 1, 0, 2 ]
// #3[
//   2, 1, 0, 1,
//   1, 3, 1, 1
// ]



82. 백신 접종

코로나 백신이 개발되어, 회사는 전 직원들에게 백신 주사를 접종하기로 하였다.
접종의 혼란을 줄이기 위하여, 부스 배정기(Hash 함수)를 사용하여 직원 이름 별로 접종할 부스를 사전에 예약 시켰으나,
몇몇 직원이 오지 않아 남는 부스가 생겨나게 되었다.
코로나 확산을 빠르게 막기 위해, 온 순서대로 부스 배정을 시키고, 사용 중이라면 다음 번호 부스로 배정 시킬 수 있도록 프로그램을 제작하시오.
예를 들어, Alice 1번, Bob은 3번에 배정되었고, 2번 부스가 비어 있는 상황에, 1번으로 배정 받은 다음 대기가 Tom은 2번에 배정되어 백신 주사를 맞게 된다.
입력은 직원들 이름으로 된 배열이 주어지고, 직원 별 주사를 맞을 부스 번호를 기록해 반환한다. (부스 번호 1번부터 시작)

function Element(key, value) {
  this.key = key;
  this.value = value;
}
function HashTable(size) {
  this.size = size;
  this.table = new Array(this.size);
  this.length = 0;
}

HashTable.prototype.hashCode = function (key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % this.size;
};

HashTable.prototype.put = function (key) {
  let index = this.hashCode(key);
  let startIndex = index;
  do {
    if (this.table[index] === undefined) {
      this.table[index] = new Element(key, true);
      this.length++;
      return true;
    }
    index = (index + 1) % this.size;
  } while (startIndex !== index);
  return false;
};

HashTable.prototype.get = function (key) {
  let index = this.hashCode(key);
  let startIndex = index;
  do {
    if (this.table[index] !== undefined && this.table[index].key === key) {
      return index;
    }
    index = (index + 1) % this.size;
  } while (startIndex !== index);
  return undefined;
};

function answer(name) {
  let result = [];
  // 구현
  let ht = new HashTable(name.length);
  for (let i = 0; i < name.length; i++) {
    ht.put(name[i]);
  }
  for (let i = 0; i < name.length; i++) {
    result.push(ht.get(name[i]) + 1);
  }
  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  ["Mana", "Naomi", "Lelia", "Morris", "Madonna"],
  ["Oliver", "Mabel", "Nero", "Rei", "Kara", "Jordan", "Nami"],
  [
    "Ruby",
    "Robin",
    "Jordan",
    "Kori",
    "Rei",
    "Madonna",
    "Justin",
    "Maya",
    "Lakia",
    "Kali",
  ],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i]));
}

// #1[ 2, 1, 3, 4, 5 ]
// #2[
//   3, 6, 7, 2,
//   1, 5, 4
// ]
// #3[
//   9, 7, 8, 6, 10,
//   3, 1, 4, 5,  2
// ]