Hash Algorithm - 완주하지 못한 선수

오랜만에 글을 써본다. 최근에는 여러 이력서를 넣으면서, 코딩 테스트를 위해 알고리즘과 자료구조에 대해서 공부 중에 있었다. 공부 내용을 정리하고 싶었지만, 해당 교육 프로그램에서는 정리 내용을 블로그라도 적으면 안된다고 해서 일주일 넘게 블로그를 작성하지 못하고!

어느정도 교육을 듣고 프로그래머스에서 코딩 문제를 풀기 시작했다.
배운 알고리즘 중에 Hash Algorithm 문제가 있어서 도전을 했고, 문제를 해결했다.

완주하지 못한 선수

participant이라는 파라미터에는 마라톤 참가자가 있는 배열이며,
completion는 완주자가 들어있는 배열이다. 참가자의 이름은 중복될 수 있으며, 완주자도 동일하게
중복될 수 있는 조건이다. solution을 통해서 완주하지 못한 선수를 return 하면 된다.

개인 해결 답

사용한 언어는 Javascript로 진행했다.

function solution(participant, completion) {
  let answer = '';
  const cH = new Map();
  for (let x of completion) {
    if (!cH.has(x)) cH.set(x, 1);
    else cH.set(x, cH.get(x)+1);
  }
  for (let x of participant) {
    if (cH.has(x)) {
      cH.set(x, cH.get(x)-1);
      if (cH.get(x) === 0) cH.delete(x);
    }
    else {
      answer += x;
    }
  }
  return answer;
}

해결 과정에서는 Map 이라는 생성자를 사용했다.

Map 객체는 키-값 쌍을 저장하며 각 쌍의 삽입 순서도 기억하는 콜렉션입니다. 아무 값(객체와 원시 값)이라도 키와 값으로 사용할 수 있습니다. -MDN-

MDN 참고자료

이번 알고리즘의 교육을 들으면서 웹 작업에 사용하지 않았던(?) 심지어 몰랐던 그런 기능까지 배워서 도움이 많이 됐다. 그 중 하나가 Map이라는 생성자다.

Map

// 아래 마라톤 완주자 배열 예시
const completion = ['A', 'B', 'C', 'D'];

// Map 사용 방법은 아래와 같다.
const mo = new Map();

// for of문으로 반복하여 completion의 요소를 하나씩 넣는다.
for (let x of completion) {
  // has는 mo라는 Map 객체 생성자 안에 x가 있는지 여부를 알려준다. (!) 니까 없을 경우에~
  // set은 말 그래도 새로운 값을 추가해준다.
  // get은 set이 되어있는 요소의 값이다.
  if (!mo.has(x)) mo.set(x,1);
  else mo.set(x, mo.get(x)+1); // 완주자 중 이름이 중복이 될 수 있으므로 +1를 해준다.
}

// mo를 출력하면, 아래와 같이 요소가 출력된다.
console.log(mo);

/*
    'A' - 1,
    'B' - 1,
    'C' - 1,
    'D' - 1,
*/

위 처럼 Map은 Key와 Value를 저장하는 콜렉션이라고 하는데 바로 이러한 형태를 가진다.
언뜻 보면 배열처럼 사용하는 듯 보이지만, 실제 배열의 내장된 함수는 사용은 안된다.

추가적으로 아래는 해결했던 답 중 완주자와 완주하지 못한 선수를 처리하는 코드이다.

for (let x of participant) {
  if (cH.has(x)) { // 기존 cH라는 Map에 x라는 선수가 있다면~
    cH.set(x, cH.get(x)-1); // set과 get을 통해 그 선수의 값에 -1를 해준다.
    if (cH.get(x) === 0) cH.delete(x); // 만약 cH의 x라는 선수 값이 0이라면 삭제
  }
  else { // cH에 입력받은 참가자 선수명이 없다면? 완주하지 못한 선수이므로 answer에 추가
    answer += x;
  }
}

위 코드의 간단하게 설명을 하자면,

1. cH라는 완주자 명단에 x라는 참가자 이름이 있는지 없는지 has로 체크
2. 체크 후 있다면? cH 명단에서 -1을 하여 재 세팅을 해준다. 2면 -> 1, 1면 -> 0
3. cH 명단에서 value가 0인 선수는 delete 해준다. (완주자 명단에서 제거)
4. 체크 후 없다면? 당연히 완주하지 못한 선수니까 answer에 이름을 추가한다.

여기서 delete라는 메소드는 말 그래도 Map 안에 있는 Key를 제거하는 역할을 한다.

이렇게 프로그래머스의 완주하지 못한 선수에 대해서 풀이 과정을 정리했다.
풀이 후 다른 사람들의 답을 보고 놀라기도 했다. 한줄로 해결을 할 줄이야...

그리고 조금씩 도전 중이다! 모른다고 포기하지 말고, 해답을 위해 구글링을 해보거나
답에 대해서 봤다면, 그 코드를 뜯어보고 이해해보고, 다시 내가 아는 지식으로 재조립도 해보면서
경험해보려고 한다.