180926 TIL

Sep 26, 2018 » 1막, TIL (Today I Learned), 코드스쿼드

알고리즘 풀기

완주하지 못한 선수
답은 나왔는데 효율성 테스트에서 떨어졌다.

function solution(participant, completion) {
    for (let i = 0; i < participant.length; i++) {
        if (completion.includes(participant[i])) {
            let value = participant[i];
            participant.splice(i, 1);
            completion.splice(completion.indexOf(value), 1);
            i--;
        }
    }
    return participant.join('');
}

이에 대한 R님의 피드백

2번 라인의 loop 밑에서 3번 라인의 includes를 사용하게 되면 전체 알고리즘이 n^2이 되어서 효율성 테스트에서 실패한 것이 아닐까 싶습니다

따라서 participant에 대한 loop를 돌면서 loop에 해당하는 검사를 수행해서는 안 됩니다

또한 배열 특성상 5번 라인의 splice 역시 배열을 순회해야 하는 메소드일 것이라 예상됩니다 (이 역시 n에 해당하므로 알고리즘적으로는 loop + n 이 되면서 n^2)

6번 라인의 경우 splice 안에서 indexOf가 사용되고 있으니 n^2에 해당할 것 같습니다 (바깥에 루프가 이미 n이라는 측면에서 해당 라인은 n^3일지로 모르겠습니다)

힌트를 어디까지 원하시는지 몰라서 코드까지는 공유드리지 않도록 하고, 한 가지만 말씀드리자면 자료구조상 이 문제를 풀기에 배열이 적합하지 않으니 participant, completion간 비교를 하실 때 배열이 아닌 자료구조를 사용하시는 것을 고려해보시길 권해드리고 싶습니다

결국 배열을 이용해서 풀어야 하는데… 다시 풀어봐야지!
코드스쿼드에는 친절하신 분들이 넘 많다. ㅠ_ㅠ