내가 해시테이블을 사용한 건가?

문제 : 프로그래머스 레벨 1 - 가장 많이 받은 선물

 

나의 풀이

우선 본론부터 말하자면 이번 문제에 대한 나의 풀이에 문제는 없다. 문제가 없을 뿐만 아니라 솔직히 다른 사람의 풀이와 비교해서 꿀리지 않는다고 생각한다. 다만 나 혼자 안고 있는 의문이 한 가지 있는데, 과연 내가 해시테이블을 사용해서 문제를 풀었다고 볼 수 있을까? 어느정도는 해시테이블을 '이용'했다고 볼 수 있을 거 같다. 그런데 해시테이블로 풀었다고 말하기는 어딘가 애매하다. 우선 전체 코드는 아래와 같다.

function solution(friends, gifts) {
  var answer = 0;
  let table = {};

  // 전체 테이블 초기화
  for (i = 0; i < friends.length; i++) {
    table[friends[i]] = {};
    table[friends[i]]["presentPoint"] = 0;

    for (j = 0; j < friends.length; j++) {
      if (i == j) continue;
      table[friends[i]][friends[j]] = 0;
    }
  }

  // 주고받고 선물지수까지 체크
  for (const i of gifts) {
    const [giver, taker] = i.split(" ");

    table[giver][taker]++;
    table[taker][giver]--;
    table[giver]["presentPoint"]++;
    table[taker]["presentPoint"]--;
  }

  // 각자 다음달에 받게 될 선물을 구하자
  for (const giver in table) {
    let temp = 0;

    for (const taker in table[giver]) {
      if (taker == "presentPoint") continue;

      if (table[giver][taker] > 0) {
        temp++;
      } else if (table[giver][taker] == 0) {
        if (table[giver]["presentPoint"] > table[taker]["presentPoint"]) temp++;
      }

      answer = Math.max(answer, temp);
    }
  }

  return answer;
}

 

규칙 분석

이 문제는 두 개의 규칙이 있는 것처럼 불릿이 되어있지만, 실은 세 개의 규칙으로 풀어가야 한다. 1) 선물을 더 준 사람이 덜 준 사람으로부터 선물 하나를 받게 되고 2) 서로 안 줬거나 서로 준 선물 갯수가 같다면 "선물지수"가 높은 사람이 낮은 사람으로부터 선물을 하나 받고 3) 선물지수를 비교해야하는 상황에서 값이 같다면 서로 안 준다는 규칙들이 그것이다.

 

테이블 초기화

이러한 규칙을 매번 전체 gifts 배열을 대상으로 처리한다는 건 말이 되지 않을 것 같았다. 해시테이블을 사용하는 것이 좋은 해결 방법이 될 거라 생각했는데, 문제는 해시테이블을 초기화하는 과정에서 이중 반복문을 사용하는 게 시간 복잡도 문제를 야기하지 않을까 걱정이 되었다. 이 부분을 꽤 고민했는데, 문제의 조건만 놓고 보면 시간 복잡도가 최대로 복잡해봤자 50^2 수준이라 그냥 이중 반복문을 쓰기로 했다.

  let table = {};

  // 전체 테이블 초기화
  for (i = 0; i < friends.length; i++) {
    table[friends[i]] = {};
    table[friends[i]]["presentPoint"] = 0;

    for (j = 0; j < friends.length; j++) {
      if (i == j) continue;
      table[friends[i]][friends[j]] = 0;
    }
  }

테이블을 초기화하는 과정에서 누가 누구에게 받고 주었는지를 확인하기 위한 필드 뿐만 아니라 각자의 선물지수를 기록할 수 있는 필드까지 만들었는데 이건 참 잘 하지 않았나 생각한다.

 

주고 받은 선물의 갯수를 기억하는가

규칙 2번을 보면 '서로 안 줬거나 서로 준 선물 갯수가 같다면'이라고 되어있다. 서로 선물을 안 줬다면 해시테이블에서 그 값이 0일 테니까, 서로 준 선물 갯수가 같을 때도 그 값이 0이었으면 좋을 것 같았다. 그 편이 나중에 2번 규칙에 해당하는지를 판단하는 로직을 짤 때 편할 테니까. 그래서 table[giver][taker]에 숫자가 하나 올라갈 때마다 table[taker][giver]에는 숫자를 하나 빼는 식으로 동작하게 했다.

또, 선물지수는 "준 선물 갯수에서 받은 선물 갯수를 뺀 값"이기 때문에 매 반복마다 선물지수를 체크하도록 했다.

  // 주고받고 선물지수까지 체크
  for (const i of gifts) {
    const [giver, taker] = i.split(" ");

    table[giver][taker]++;
    table[taker][giver]--;
    table[giver]["presentPoint"]++;
    table[taker]["presentPoint"]--;
  }

 

너는 다음달에 몇 개의 선물을 받게 될까

해시테이블에 있는 giver를 한 놈 씩 불러다가 그 놈이 몇 개의 선물을 받게될지 알아낸다. 만약 문제가 "제일 많이 받게되는 사람"을 찾아내라 요구했다면 코드가 조금 달라졌겠지만, "가장 많이 받는 놈은 몇 개의 선물을 받을까"이기 때문에 Math.max를 사용했다.

table[giver]에는 받은 놈들 목록과 "presentPoint"가 존재하기 때문에 taker가 "presentPoint"일 경우 해당 반복문을 조기 종료하도록 했다. 만약 table[giver][taker]의 값이 0보다 크다면 선물을 더 많이 줬다는 뜻이니까 temp에 1점이 올라가고, 이 값이 0이라면 서로 안 줬거나 같은 수의 선물을 줬다는 뜻이니 선물지수를 비교하도록 했다.

  // 각자 다음달에 받게 될 선물을 구하자
  for (const giver in table) {
    let temp = 0;

    for (const taker in table[giver]) {
      if (taker == "presentPoint") continue;

      if (table[giver][taker] > 0) {
        temp++;
      } else if (table[giver][taker] == 0) {
        if (table[giver]["presentPoint"] > table[taker]["presentPoint"]) temp++;
      }

      answer = Math.max(answer, temp);
    }
  }

 

결론

문제 자체는 굉장히 깔끔하게 풀었다고 생각한다. 테이블을 사용하긴 했는데 이게 '해시테이블'이 맞는지를 잘 모르겠다. 이 말은 결국 내 머릿속에 '해시테이블'의 정의가 딱 떨어지는 형태로 존재하지 않다는 방증이기도 하겠다. 기억해야할 코드는 따로 없고 그저 공부해야겠다, 가 오늘의 결론이다.