포켓몬
구명보트

공부하며 느낀 점

포켓몬

배열의 요소가 몇 종류인지를 알아내는 것이 관건일 것 같다.

나의 풀이

처음에는 조건을 잘못 줬다.

function sol0(nums) {
    const setNums = [...new Set(nums)];
    const halfOfLength = nums.length/2
    const types = setNums.length
    
    if (types >= halfOfLength){
        return halfOfLength
    } else  {
        return types
    }
}

Set을 이용하여 중복을 요소를 없앴다.
전체 길이의 절반과 포켓몬 종류의 갯수를 비교했다.
그리고 포켓몬의 종류가 더 많다면 길이 절반을 리턴
그렇지 않다면 포켓몬의 종류를 리턴

다른 사람의 풀이

function sol1(nums) {
  const max = nums.length / 2;
  const arr = [...new Set(nums)];

  return arr.length > max ? max : arr.length
}

function sol2(nums) {
    const noDuplicatePokemon = new Set(nums);
    const pokemonVarietyCount = noDuplicatePokemon.size;
    const pokemonCounts = nums.length;
    return pokemonVarietyCount > pokemonCounts/2 ? pokemonCounts/2 : pokemonVarietyCount;

}

나와 같은 풀이 방식이다.

속도 비교

시간복잡도는 모두 $O(N)$이다.

반복 횟수 100배 증가

특별한 점은 없어 보인다.

입력값 길이 10배 증가

const q = [3, 3, 3, 2, 2, 4, 7, 8, 9, 9];
  const repeatCount = 10;
  const w = Array(repeatCount).fill(q).flat();

위와 같이 10배 긴 배열을 생성하였다.

입력값 길이 100배 증가

sol2 가 제일 빨랐지만, 입력값이 커지면 시간이 늘어나는 비율이 제일 컸다. 결국 10배까지는 괜찮았는데 100배쯤에서 역전이 시작된다.

반복 횟수를 10배 줄이고 입력값 길이는 1000배로 해보자

입력값 길이 1000 배 증가

특별히 유의미한 차이는 보이지 않는다.

입력값 길이 10000 배 증가

슬슬 sol0이 제일 빨라지기 시작한다.

구명보트

최대치에 가장 가까운 합을 구해야한다.

나의 풀이

function sol0(people, limit) {
    let answer = 0;
    people.sort((a,b) => a - b)
    let lengthPeople = people.length

    while (lengthPeople > 0) {
        const length = people.length

        if ( people[0] + people[length-1] <= limit ){
            people.pop()
            people.shift()
        } else (
            people.pop()
        )
        lengthPeople = people.length
        answer ++
    }

    return answer;
}

• sort로 오름차순 정렬를 한다.
• 가장 무거운 값 people[length-1] + 가장 가벼운 값 people[0] 을 더한다.
• 이 값이 limit 이하라면 둘다 제거한다.
  * 이때 조금이라도 더 빠른 제거를 위해 pop을 먼저 실행한다.
• 그렇지 않다면 최대 값만 제거한다.

다른 사람의 풀이

function sol1(people, limit) {
    people.sort((a, b) => b - a);
    let count = 0;
    while(people.length) {
        if(people[0] + people[people.length - 1] <= limit) {
            people.shift();
            people.pop();
        }else {
            people.shift();
        }
        count++;
    }
    return count
}

나의 풀이와 개념 자체는 같지만 정렬의 순서가 반대다. 거기에 shift를 먼저했고, 아마 내 코드보다 무조건 느릴 것같다.

function sol2(people, limit) {
    people.sort(function(a, b){return a-b});
    for(var i=0, j=people.length-1; i < j; j--) {
        if( people[i] + people[j] <= limit ) i++;
    }    
    return people.length-i;
}

나의 풀이는 반복문 조건을 간단히 짤 자신이 없어서 배열 자체를 건드렸는데, 여기서는 for문으로 조건을 잘줬다. 반복문 안의 코드도 잘짰다. 배운게 많은 코드다. 내 코드보다 무조건 빠를 것같다.

속도 비교

sol0, sol1 : $O(N \log{N} + N)$
sol2 : $O(N \log{N} + N/2)$
로그의 밑은 2

반복횟수 10배 증가

아직 특별한 점은 안보인다.

입력값 길이 10배 증가

10 * 3.32 니까 최대 33배 정도 증가할것이다.

다행히도 최악의 경우의 절반밖에 증가하지 않는다.
다만 sort를 해야하는 people의 길이가 길수록 효율이 나빠질 것으로 보인다.

입력값 길이 100배 증가

100 * 6.64 = 664배까지 증가할 수 있다.

sol0 과 sol1은 약간의 순서만 바뀌었을 뿐인데 효율에서 큰 차이가 벌어지고 있다.

의외로 sol2가 sol1보다 증가율은 더 크다. 데이터의 크기가 엄청나게 크다면 sol0을 쓰는게 나을지도?

생각해보니 내 코드랑 sol2를 합친걸 안구했다. 우선 잘돌아가나 확인..

뭐야 이런거 처음봐요...

function solution(people, limit) {
    people.sort((a,b) => a - b)
    let lengthOfPeople = people.length
    let i = 0
    let j = lengthOfPeople -1
    
    while (i < j) {
        if (people[i] + people[j] <= limit) i++
        j--
    }
    
    return lengthOfPeople-i;
}

같은조건으로 반복해보자

초기 반복 시간도 작고, 증가율도 제일 적다.

공부하며 느낀 점

1. while문이 for문 보다 더 효율이 좋지만, 아직 짜는데 익숙하지 못하다.
   그러니 for문으로 먼저 짜고 while문으로 바꾸는 것으로 연습을 해야할 것같다.
2. 같은 방법을 생각했더라도 구현이 조금 달라지는 것으로 효율이 완전히 갈릴 수 도 있다.
3. 꼭 필요한 것이 아니라면 배열자체는 바꾸지 않거나 최대한 마지막에 바꾸는 것이 좋다고 느껴진다.
4. sort는 코스트가 비싸다.