과일 장수 | 예상 대진표

김민준·2023년 12월 12일

알고리즘 코드테스트 프로그래머스

코드테스트

목록 보기

18/37

과일 장수
예상 대진표

공부하며 느낀 점

과일 장수

score.length 가 m으로 나눠 떨어지지 않는 경우만 예외처리를 하면 되겠다.

근데 이거 k가 필요한 값인가?...

나의 풀이

function sol0(k, m, score) {
    const boxes = []
    let price = 0

    let length = score.length
    const amountOfBox = parseInt(length%m)
    length -= amountOfBox
    score.sort((a,b) => b - a)

    let i = 0

    while ( i < length) {
        boxes.push(score.slice(i,i+m))
        i += m
    }

    const lengthOfBoxes = boxes.length

    i = 0

    while ( i < lengthOfBoxes) {
        price += boxes[i][m-1] * m
        i ++
    }

    return price
}

sort는 오래걸리지만 할 수 밖에 없다.
아님 뭔가 다른 알고리즘을 생각하는수밖에

내림차순 정렬을 해서 비싼것부터 넣도록한다.
배열의 길이를 [배열의 길이%상자 하나에 들어가는 과일 갯수] 만큼 빼서 상자 하나를 다 못채우는 경우를 예외처리한다.

첫 번째 while문에서 상자에 과일을 담는다.

두 번째 while문에서 상자마다 가격을 계산한다.

다른 사람의 풀이

const sol1 = (_, m, s) => s.sort().filter((_, i) => !((s.length - i) % m)).reduce((a, v) => a + v, 0) * m

s.sort() : 우선 정렬을 한다.
.filter((_, i) => !((s.length - i) % m)) : 현재 인덱스에서 i 까지의 길이를 m(한박스에 담기는 과일수)로 완전히 나눌 없는 요소들을
.reduce((a, v) => a + v, 0) * m : 제거하고, 남는 값들의 첫 인덱스에 m을 곱한 값을 누적해서 더한다.

function sol2(k, m, score) {
    let answer = 0;
    const sortedScore = score.slice().sort((a, b) => a - b).slice(score.length % m);
    for (let i = 0; i < sortedScore.length; i += m) {
        answer += sortedScore[i] * m;
    }
    return answer;
}

나와 생각이 같은데 더 효율적이다.

포장이 안될 녀석들을 걸러내는 과정이 더 효율적이다.
아마 slice를 쓰는 횟수에서 차이가 나서 속도 차이가 클 것이다.

속도 비교

시간복잡도는 모두 $O(N \log{N})$ 이다

반복 횟수 10회 증가

sol0과 sol1은 거의 같은 개념임에도 구체적으로 구현한 방법의 차이 때문에 속도의 차이가 크다.

입력값 길이 10배 증가

딱히 주목할만한 변화가 없다.

예상 대진표

모든 수를 2n 단위로 생각하고 (2n-1)로 만든다.
이것을 반복한뒤 A, B가 같은 2n 단위안에 들어오면 그때까지 거친 횟수를 리턴한다.

나의 풀이

function sol0(n,a,b)
{
    let answer = 1

    while (Math.ceil(a/2) != Math.ceil(b/2) ) {
        a = Math.ceil(a/2)
        b = Math.ceil(b/2)
        answer ++
    }

    return answer;
}

의식의 흐름대로 풀어냈다.

다른 사람의 풀이

function sol1(n,a,b)
{
    let answer = 0;
    while(a !== b) {
        a = Math.ceil(a/2);
        b = Math.ceil(b/2);
        answer++;
    }

    return answer;
}

나랑 같은 방법인데 while문의 조건이 더 간결하다. 이게 더 좋은 것같다.

function sol2(n,a,b)
{
    var mid = (n + 1) / 2

  if (a > mid && b < mid) {
    return Math.log2(n)
  } else if (a < mid && b > mid) {
    return Math.log2(n)
  } else {
    if(a < mid && b < mid){
      return solution(n / 2, a, b)
    } else{
      return solution(n / 2, a-(n/2), b-(n/2))
    }
  }

}

문제의 조건에서 2의 지수로 n의 길이가 결정된다고 하였음으로 (n+1)/2 로 정 중앙을 잡고 a와 b가 서로 반대편에 있으면 2를 밑으로하는 로그에 취해서 횟수를 구한다.

그렇지 않고 한쪽에 몰려 있다면 범위를 반으로 줄여서 자기 자신을 재귀적으로 불러낸다.

아마 a,b가 3,4 처럼 딱 붙은 경우에는 sol2가 느리지만 100개중에서 1,100 처럼 반대편 극단에 있는 경우에는 sol2가 빠를것이다.

속도 비교

시간 복잡도는 모두 $O(\log{n})$ 이다.
sol0, sol1 : 반복할때마다 연산량이 반으로 줄어듬
sol2 : 재귀적으로 호출 될때마다 연산량이 반으로 줄어듬

속도 비교 방법 변경

원래는 항상 같은 입력값을 줬는데 랜덤하게 바꾸었다.
이유는 sol2과 나머지가 유리하고 불리한 조건이 반대이기 때문

async function runSolutionWithTiming(solutionFn, q) {
  const n = 1000000;
  const f = 100;

  const startTime1 = new Date();
  for (let i = 0; i < n; i++) {
    getRandomNumbers(q);
    await solutionFn(q, a, b);
  }
  const endTime1 = new Date();
  const executionTime1 = endTime1 - startTime1;

  const startTime2 = new Date();
  for (let i = 0; i < n * f; i++) {
    getRandomNumbers(q);
    await solutionFn(q, a, b);
  }
  const endTime2 = new Date();
  const executionTime2 = endTime2 - startTime2;

  const multiple = (executionTime2 / executionTime1)
    .toFixed(2)
    .toString()
    .padStart(5, " ");

  console.log(
    `반복횟수 ${n}에서 ${f}배 증가시 작동시간 ${multiple}배로 증가  ${solutionFn.name} | ${executionTime1}ms → ${executionTime2}ms`
  );
}

//

let a = 0;
let b = 0;

function getRandomNumbers(n) {
  if (n < 2) {
    console.log("n은 2 이상이어야 합니다.");
    return;
  }

  a = Math.floor(Math.random() * n) + 1;
  b = Math.floor(Math.random() * n) + 1;

  while (a === b) {
    b = Math.floor(Math.random() * n) + 1;
  }

  return [a, b];
}

async function main() {
  const n = Math.pow(2, 5);
  await runSolutionWithTiming(sol0, n);
  await runSolutionWithTiming(sol1, n);
  await runSolutionWithTiming(sol2, n);
}