가장 많이 받은 선물 -JS

이 문제는 풀다가 중도 포기를 하게 되었다.

그 이유는 문제를 풀다보니 for문과 변수 선언을 너무 많이하게 되서 결국 포기를하고 다른 사람의 풀이를 보면서 어떻게 풀었는지 이해를 하기로 하였습니다.

 

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/258712

프로그래머스

 

풀이 코드

function solution(friends, gifts) {
    let N = friends.length;
    //친구들 이름에 따른 idx map 에 저장
    const nameMap = new Map();
    //친구들끼리 주고받은 선물 내역 저장
    const giftTable = Array.from({length: N}).map(() => new Array(N).fill(0));
    console.log(giftTable);
    //선물지수 계산하는 1차원 배열
    const rankInfo = new Array(N).fill(0);
    const nextMonth = new Array(N).fill(0);
    
    //친구들의 이름과 idx를 map에 set 한다.
    friends.forEach((name, idx) => {
        nameMap.set(name, idx);
    })
    
    
    //선물 내역 저장
    gifts.forEach((info) => {
        const [from, to] = info.split(' ');
        giftTable[nameMap.get(from)][nameMap.get(to)]++;
    })
    
    // 선물 지수 계산
    for (let i=0; i<N; i++){
        // i줄은 선물을 줬으니 +1
        rankInfo[i] = giftTable[i].reduce((a,b) => a+b, 0);
        // j줄은 선물을 받은 것이니, 기존 선물지수에서 -1 을 한다.
        for(let j = 0; j<N; j++){
            rankInfo[i] -= giftTable[j][i];
        }
    }
    
    //다음달 받을 선물 수 계산
    for (let i = 0; i<N; i++){
        for (let j = i+1; j<N; j++) {
            if (i === j) continue;
            //두 사람이 선물을 주고받은 기록이 있다면
            if (giftTable[i][j] > giftTable[j][i]) nextMonth[i]++;
            if (giftTable[i][j] < giftTable[j][i]) nextMonth[j]++;
            //두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면
            if (giftTable[i][j] === giftTable[j][i]) {
                //두 사람이 선물을 주고받은 기록이 있다면
                if(rankInfo[i] > rankInfo[j]) nextMonth[i]++;
                if(rankInfo[i] < rankInfo[j]) nextMonth[j]++;
                //두 사람이 선물을 주고받은 기록이 없다면
            }
        }
    }
    console.log(nameMap);
    console.log(giftTable);
    console.log(rankInfo);
    console.log(nextMonth);
    
    return Math.max(...nextMonth);
}

 

풀이 해설이 물론 주석처리로 해결이 되었지만 제가 아직 익숙하지 않은 메서드들이 있습니다.

그 부분을 중점으로 설명하겠습니다.

 

    //친구들 이름에 따른 idx map 에 저장
    const nameMap = new Map();
    //친구들끼리 주고받은 선물 내역 저장
    const giftTable = Array.from({length: N}).map(() => new Array(N).fill(0));
    console.log(giftTable);

첫번째로 Map의 사용법이었습니다.

Map은 원본배열을 가만히 두고 새로운 배열을 return해줍니다.

const giftTable = Array.from({length: N}).map(() => new Array(N).fill(0));

위의 코드를 분리해서 설명하겠습니다.

Array.from({length: N})

일단 길이 N의 배열을 만들어 줍니다.

.map(() => new Array(N).fill(0));

map을 이용해서 앞에서 N의 길이를 가진 배열안에 데이터를 저장할 수 있는 공간에 길이 N짜리 배열에 0을 채워넣어주는 겁니다.

즉, 길이 N짜리 배열을 만든 후 만든 배열안에 데이터를 넣을 수 있는 공간 N개가 있는데 각각에 새로운 배열 N을 생성 후 0값을 넣어줍니다.

이렇게하면 Table N x N짜리가 0으로 채워져 있는것으로 나타내집니다.

ex) 만약 N이 4라면

giftTable = [ [ 0, 0, 0, 0 ],

                    [ 0, 0, 0, 0 ],

                    [ 0, 0, 0, 0 ],

                    [ 0, 0, 0, 0 ] ]

이렇게 만들어 지는 겁니다.

이 방법을 몰라서 for문을 몇개를 돌렸는지 이중배열선언하고 후우....

 

여기서 주의해야할 점은 nameMap이랑 giftTable은 Map으로 만들어진 배열이기 때문에 일반 배열처럼 사용하는게 아닙니다. 

Map의 사용법을 알아야 합니다.

• new Map() – 맵을 만듭니다.
• map.set(key, value) – key를 이용해 value를 저장합니다.
• map.get(key) – key에 해당하는 값을 반환합니다. key가 존재하지 않으면 undefined를 반환합니다.
• map.has(key) – key가 존재하면 true, 존재하지 않으면 false를 반환합니다.
• map.delete(key) – key에 해당하는 값을 삭제합니다.
• map.clear() – 맵 안의 모든 요소를 제거합니다.
• map.size – 요소의 개수를 반환합니다.

    //친구들의 이름과 idx를 map에 set 한다.
    friends.forEach((name, idx) => {
        nameMap.set(name, idx);
    })

firends라는 배열을 forEach문을 통해서 매개변수 name, idx를 가져와서 친구들의 이름과 index를 닮을 nameMap에 넣어줍니다.

이걸 해주는 이유는 index를 통해서 누가 누구인지 알기 쉽기 때문입니다.

친구들 이름에 따른 index map을 생성을 하면 줄 사람이랑 받을 사람의 index를 통해서 누가 누구인지 쉽게 파악하기 때문입니다.

 

이렇게 친구들의 이름과 index로 map으로 배열을 만들어 냈으면 이번달에 누가 누구에게 선물을 줬는지 저장을 해줍니다.

    //선물 내역 저장
    gifts.forEach((info) => {
        const [from, to] = info.split(' ');
        giftTable[nameMap.get(from)][nameMap.get(to)]++;
    })

여기서 [from, to] 이런식으로 배열을 만들어서 저장하는 법에 대해서도 처음 알았습니다.

일단 누가 누구에게 줬는지가 배열안에 string으로 저장이 되어 있고 각 이름이 "muzi frodo", 이런식으로 빈 공간을 통해서 나눠져 있기 때문에 from이라는 것에는 선물을 준 사람 to는 선물을 받은 사람이 담겨집니다.

const [from, to] = info.split(' ');

따라서 여기 안에 만약에 info가 "muzi frodo"가 들어온다면 const [from, to] = ['muzi', 'frodo']로 들어가는 것이고

from = 'muzi , to = 'frodo' 입니다.

giftTable[nameMap.get(from)][nameMap.get(to)]++;

이제 이부분은 아까만든 NxN Table인 giftTable의 nameMap.get(from) = nameMap에 있는 from의 이름값의 index가 나오게 되고 첫번째 나온 index 행의 두번째 누구에게 주었는지에 대한 열에관한 nameMap.get(to) 누구에게 주었는지에 대한 index를 통해서 결국 giftTable[nameMap.get(from)][nameMap.get(to)] === giftTable[선물 준 사람의 index][선물 받은 사람의 index]가 들어가게 되고 그럼 배열의 value값이 처음에는 0이니까 ++ 증감연산자를 통해서 1이 됩니다.

이렇게 누가 누구에게 선물을 몇개 줬는지를 forEach를 통해서 보기 편한 Table로 나타내집니다.

 

이제 누가 누구한테 선물을 몇개를 줬는지 giftTable에 저장이 되었으니 선물 지수를 계산해 줍니다.

 

    // 선물 지수 계산
    for (let i=0; i<N; i++){
        // i줄은 선물을 줬으니 +1
        rankInfo[i] = giftTable[i].reduce((a,b) => a+b, 0);
        // j줄은 선물을 받은 것이니, 기존 선물지수에서 -1 을 한다.
        for(let j = 0; j<N; j++){
            rankInfo[i] -= giftTable[j][i];
        }
    }

여기서 rankInfo란 선물지수를 계산하기 위한 1차원 배열입니다.

만약 friends = ["muzi", "ryan", "frodo", "neo"] 라고 한다면 rankInfo[0]은 muzi의 선물지수를 나타내는 것이고

giftTable[0]은 muzi가 누구한테 선물을 몇개 줬는지에 대한 배열이 나오게 되는 겁니다.

그럼 선물지수 = 내가 준 선물 개수 - 내가 받은 선물 개수이기 때문에 일단

rankInfo[i] = giftTable[i].reduce((a,b) => a+b, 0);

위의 코드에 의해 내가 준 선물 개수의 총 합을 구해 줍니다.

여기서 reduce 메서드를 알아야 하는데

1. callback function
   
   • 다음 4가지의 인수를 가집니다.
     1. accumulator - accumulator는 callback함수의 반환값을 누적합니다.
     2. currentValue - 배열의 현재 요소
     3. index(Optional) - 배열의 현재 요소의 인덱스
     4. array(Optional) - 호출한 배열
   • callback함수의 반환 값은 accumulator에 할당되고 순회중 계속 누적되어 최종적으로 하나의 값을 반환합니다.
2. initialValue(Optional)
   • 최초 callback함수 실행 시 accumulator 인수에 제공되는 값, 초기값을 제공하지 않을경우 배열의 첫 번째 요소를 사용하고, 빈 배열에서 초기값이 없을 경우 에러가 발생합니다.

반환 값

배열을 순서대로 불러 각 요소에 대해 callback 함수을 실행한 결과를 누적한 값

[출처 : https://tocomo.tistory.com/26]

rankInfo[i] = giftTable[i].reduce((a,b) => a+b, 0);

여기서 reduce a는 accumulator이고 b는 currentValue그리고 0은 initialValue입니다.

따라서 giftTable의 각 배열에 있는 요소들을 다 더한 값이 rankInfo로 넘어가게 됩니다.

이제 내가 받은 선물 개수를 빼주면 선물 지수가 나옵니다.

        for(let j = 0; j<N; j++){
            rankInfo[i] -= giftTable[j][i];
        }

위의 코드가 내가 받은 선물 개수를  빼주면 rankInfo에 각 사람의 선물지수가 나오게 됩니다.

 

이제 이 문제의 return값을 구하기 위해서 결국 다음달에 누가 몇개를 받는지를 알아야 합니다.

    //다음달 받을 선물 수 계산
    for (let i = 0; i<N; i++){
        for (let j = i+1; j<N; j++) {
            if (i === j) continue;
            //두 사람이 선물을 주고받은 기록이 있다면
            if (giftTable[i][j] > giftTable[j][i]) nextMonth[i]++;
            if (giftTable[i][j] < giftTable[j][i]) nextMonth[j]++;
            //두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면
            if (giftTable[i][j] === giftTable[j][i]) {
                //두 사람이 선물을 주고받은 기록이 있다면
                if(rankInfo[i] > rankInfo[j]) nextMonth[i]++;
                if(rankInfo[i] < rankInfo[j]) nextMonth[j]++;
                //두 사람이 선물을 주고받은 기록이 없다면
            }
        }
    }

위의 코드는 문제 설명인 두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.
두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.
선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값입니다.
만약 두 사람의 선물 지수도 같다면 다음 달에 선물을 주고받지 않습니다.

이 부분을 코드화 한 것입니다.

 

마지막으로

return Math.max(...nextMonth);

예전글에서 말한 spread syntax를 이용하여 최대값을 찾아서 리턴해주면 됩니다.

 

정말.. 이 문제 하나때문에 3시간을.. 날렸다고 생각하니 머리가 아프군요.