[프로그래머스] 가장 많이 받은 선물 (Javascript)

문제

[프로그래머스] 가장 많이 받은 선물

풀이

문제 정의

친구들이 있고, 친구들끼리는 매달 선물을 주고 받는다.
두 친구가 이번 달에 선물을 주고받은 횟수를 비교하여 둘 중 선물을 더 많이 받은 친구가 선물을 더 적게 받은 친구에게 다음 달에 선물 하나를 준다.

예를 들어 A와 B가 있다고 가정하고, 이번 달에A가 B에게 선물을 5개 보냈고, B가 A에게 선물을 3개 보냈다면 다음 달에는 B가 A에게 선물을 하나 줘야 한다.

만약 두 친구가 선물을 주고받은적이 없거나, 주고받은 횟수가 없거나 동일하다면 선물 지수가 작은 친구가 선물 지수가 큰 친구에게 다음달에 선물을 하나 줘야 한다.

선물 지수란 "선물을 보낸 횟수 - 선물을 받은 횟수"이다.
만약 선물 지수도 같다면 두 사람을 다음달에 선물을 주고받지 않는다.

friends 배열에 친구들의 이름이 있고, gifts 배열에 친구들 끼리 선물을 주고 받은 기록이 있을 때, 다음달에 선물을 가장 많이 받을 친구가 받을 선물의 개수를 구하시오.

gifts[i]가 "A B"라면 A가 B에게 선물을 보낸 것이다.

해결방안

우선 누가 누구에게 선물을 몇개 보냈는지 알아야 한다.

위 이미지는 입출력 예시 설명에 나와있는 관계형 테이블인데, 위 이미지처럼 2차원 배열을 이용하면 될 것 같다.

위 이미지에서 배열의 키값이 친구들의 이름(문자열)으로 되어 있지만 실제로 배열의 값에 접근할 때는 인덱스(숫자)를 사용해야 한다.

따라서 친구들의 이름과 인덱스를 매칭시켜줄 객체를 만든다.

const idx = {};
friends.forEach((name,i)=>idx[name] = i);

idx 객체는 친구의 이름을 key로, 인덱스를 value로 갖는다.

이제 2차원 배열을 만들어보자.

const N = friends.length;
const giftRecord = Array.from(Array(N),()=>Array(N).fill(0));

for(const record of gifts){
    let [send, receive] = record.split(' ');
    send = idx[send]
    receive = idx[receive];
    giftRecord[send][receive]++; // send가 receive에게 선물을 보낸 횟수
}

입력으로 주어진 gifts 배열의 값을 순서대로 꺼내며 공백을 기준으로 "보낸사람"과 "받은사람"을 분리하고 이름과 인덱스를 변환시킨뒤 2차원 배열에 값을 저장해준다.

또한 선물을 주고 받은 횟수가 같을 때는 선물 지수를 이용해서 비교해야 하므로 선물 지수를 담을 배열도 만들어준다.

...
const giftIndex = Array(N).fill(0);

for(const record of gifts){
    ...
    giftIndex[send]++; // 보낸 횟수
    giftIndex[receive]--; // 받은 횟수
}

이로써 준비는 끝났고 이제 조건에 맞게 다음달에 친구들이 받을 선물의 개수를 누적해주면 된다.

for(let i of friends){
    i = idx[i];
      for(let j of friends){
        j = idx[j]
        if(i===j) continue;
        if(giftRecord[i][j] > giftRecord[j][i]) nextMonth[i]++; // i가 j에게 준 선물이 더 많다면 i가 하나 받는다.
        else if(giftRecord[i][j] === giftRecord[j][i]) { // 둘다 보낸 기록이 없거나(0) 주고받은 횟수가 같을 경우 선물 지수를 비교한다.
          if(giftIndex[i] > giftIndex[j]) nextMonth[i]++; // i의 선물지수가 더 높다면 i가 하나 받는다.
        }
    }
}

자기 자신한테 선물을 주고 받는 경우는 없으므로 i===j일때는 무시하고 다음으로 넘어간다.
nextMonth에 값을 전부 누적한 뒤에는 nextMonth에서 가장 큰 값을 출력하면 된다.

answer = Math.max(...nextMonth);
return answer;