[알고리즘] 나 그래도 풀긴 풀었어...?

🐾들어가며

- 프로그래머스 코딩테스트 > 2024 KAKAO WINTER INTERNSHIP > 가장 많이 받은 선물

문제: 이번 달의 선물 기록을 바탕으로 다음 달에 선물을 누가 많이 받을지 예측하기

조건

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

입력

• 친구들의 이름을 담은 1차원 문자열 배열 friends
• 이번 달까지 친구들이 주고받은 선물 기록을 담은 1차원 문자열 배열 gifts

출력

• 다음달에 가장 많은 선물을 받는 친구가 받을 선물의 수

 

✨본격적으로

내가 쓴 코드

function solution(friends, gifts) {
    const graph = {};
    const index= {};
    const next = {};
    
    //init graph
    friends.forEach((f,i)=>{
        graph[f] = {}
        friends.forEach((fi,i)=>{
            if(fi != f) graph[f][fi] = gifts.filter(ig => (ig.split(" ")[0] === f) && fi === ig.split(" ")[1]).length;
        })
    })
    //distance
    friends.forEach((f,i)=>{
        next[f] = 0;
        gifts.forEach((gift, k)=>{
            const g = gift.split(" ");
            const receive = gifts.filter(ig => ig.split(" ")[0] === f).length;
            const give = gifts.filter(ig => ig.split(" ")[1] === f).length;
            index[f] = receive - give;
        })
    })
    //next month
    friends.forEach((f, i)=>{
        friends.forEach((fi, ii)=>{
            const g = graph[f][fi];
            const r = graph[fi][f];
            
            if((!!g || !!r) && g > r) next[f]++;
            if(g === r && index[f] > index[fi]) next[f]++;
            
        })
    })
    
    const value = Object.values(next);
    return Math.max(...value);
}

결과: 테스트는 통과... 실패는 모두 `시간 초과`

실행 결과

스스로 생각한 이유는 중첩 반복을 문제로 보았습니다.  심지어 그 안에서 filter까지 쓰고 있어서 3번 중첩이라고 봐야 합니다. 그리고... ChatGPT야 내 코드를 분석해줘.

1. 선물 주고받은 횟수 계산:
   • gifts 배열을 여러 번 순회하여 filter를 사용하는 대신, 단일 순회로 선물 주고받은 횟수를 미리 계산해놓고 사용하는 것이 더 효율적입니다.
2. 선물 지수 계산:
   • 선물 주고받은 횟수를 미리 계산해놓으면, 선물 지수도 빠르게 계산할 수 있습니다.
3. 다음 달 선물 받을 횟수 계산:
   • 선물 주고받은 횟수와 선물 지수를 미리 계산해두면, 이 값을 이용해 한 번에 비교하고 계산할 수 있습니다.

앗.. 최적화한 코드까지 나와 보고 말았습니다. 다음부턴 포인트만 받아서 직접 고쳐보겠습니다.

먼저 `graph`입니다.

    //init graph
    friends.forEach((f,i)=>{
        graph[f] = {}
        friends.forEach((fi,i)=>{
            if(fi != f) graph[f][fi] = gifts.filter(ig => (ig.split(" ")[0] === f) && fi === ig.split(" ")[1]).length;
        })
    })

처음에 사실 문제 이해가 잘 되지 않아서 입출력 예시에 대한 설명에서 표처럼 나온 것을 그대로 그려보려고 했던 것이 큰 흠이었습니다. 실질적으로 그래프는 마지막에 비교하기 위해 사용할 뿐인데 너무 많은 시간을 그래프를 그리는 데 할애하고 있었습니다. 문제에서 실질적으로 중요한 요소는 `누구`가 아닌 `횟수`입니다.

👉graph 삭제!

따라서 `index`입니다.

    //distance
    friends.forEach((f,i)=>{
        next[f] = 0;
        gifts.forEach((gift, k)=>{
            const g = gift.split(" ");
            const receive = gifts.filter(ig => ig.split(" ")[0] === f).length;
            const give = gifts.filter(ig => ig.split(" ")[1] === f).length;
            index[f] = receive - give;
        })
    })

여기에서도 3중첩입니다... 바로바로 receive와 give의 횟수를 만들고 있습니다. 심지어 2번째 중첩은 필요가 없습니다.

    //distance
    friends.forEach((f,i)=>{
        next[f] = 0;
        const receive = gifts.filter(ig => ig.split(" ")[0] === f).length;
        const give = gifts.filter(ig => ig.split(" ")[1] === f).length;
        index[f] = receive - give;
    })

그래도 아직 중첩 반복입니다. filter를 확실히 없애기 위해 receive와 give를 별도로 선언해 주어야 겠습니다. 또한 초기화 부분은 별도로 빼주었습니다.

👉 `receive`, `give` 별도 선언, 초기화 분리

    const index= {};
    const next = {};
    const receive = {};
    const give = {};
    
    //init graph
    friends.forEach((f,i)=>{
        next[f] = 0;
        receive[f] = 0;
        give[f] = 0;
    })
   
    //distance
    gifts.forEach((gift, k)=>{
        const g = gift.split(" ");
        receive[g[1]]++;
        give[g[0]]++;
    })

중첩 반복이 사라졌다...!

그리고 `graph`를 대체해줍니다.

    //next month
    friends.forEach((f, i)=>{
        friends.forEach((fi, ii)=>{
            const g = graph[f][fi];
            const r = graph[fi][f];
            
            if((!!g || !!r) && g > r) next[f]++;
            if(g === r && index[f] > index[fi]) next[f]++;
            
        })
    })

기존에 그래프가 쓰인 부분입니다. 이 부분은 GPT의 코드를 빌려왔습니다(사실 전체 다 빌려왔다..) 바로 filter를 사용해 다음과 같이 바꾸었습니다. 계속 split을 사용해서 입력받은 것을 바꿔야지만 생각하다가 입력받은 그대로를 비교하려는 생각은 못한 것 같습니다.

👉 입력받은 대로 비교

    //next month
    friends.forEach((f, i)=>{
        friends.forEach((fi, ii)=>{
            const g = gifts.filter(gift => gift === `${f} ${fi}`).length;
            const r = gifts.filter(gift => gift === `${fi} ${f}`).length;
            
            if((g || r) && g > r) next[f]++;
            if(g === r && index[f] > index[fi]) next[f]++;
            
        })
    })

✔️결론

오랜만에 코딩테스트를 풀다보니 문제 이해부터 난이도가 있었고, 정확히 어떤 것을 변수로 선언해야 하는지도 애먹었던 문제였습니다. 코딩테스트는 꾸준히 풀어야 겠습니다. 중첩 반복을 사용한다면 너무 복잡하게 생각하는 것이 아닌지 계속 의심해보기도 해야겠습니다.

최종 코드

function solution(friends, gifts) {
    const index= {};
    const next = {};
    const receive = {};
    const give = {};
    
    //init graph
    friends.forEach((f,i)=>{
        next[f] = 0;
        receive[f] = 0;
        give[f] = 0;
    })
   
    //distance
    gifts.forEach((gift, k)=>{
        const g = gift.split(" ");
        receive[g[1]]++;
        give[g[0]]++;
    })
    
    friends.forEach(f => {
        index[f] = give[f] - receive[f];
    });
    
    //next month
    friends.forEach((f, i)=>{
        friends.forEach((fi, ii)=>{
            const g = gifts.filter(gift => gift === `${f} ${fi}`).length;
            const r = gifts.filter(gift => gift === `${fi} ${f}`).length;
            
            if((g || r) && g > r) next[f]++;
            if(g === r && index[f] > index[fi]) next[f]++;
            
        })
    })
    
    const value = Object.values(next);
    return Math.max(...value);
}