Leetcode Java Poor Pigs

문제

Link

코드

class Solution {

  public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int pigs = 0;
    while (Math.pow((minutesToTest / minutesToDie) + 1, pigs) < buckets) {
      pigs++;
    }
    return pigs;
  }

}

결과

Link

설명

1. minutesToTest 시간(분) 동안 테스트를 수행하여 어떤 양동이가 독성이 있는지 확인하기 위한 최소한의 돼지의 수를 구하는 문제이다.
   • buckets 개수의 양동이 내 독성이 있는 양동이가 하나 포함되어 있는데 이 독성은 minutesToDie 시간(분)이 지나면 효과가 발생하여 돼지가 죽는다.
   • minutesToTest 시간(분)까지 아래 과정을 반복한다.
     • 돼지를 골라 먹이를 줄 양동이를 선택하여 모두 소비하고, 다른 돼지들에게 먹이를 주지 않는다.
     • 먹이를 먹은 후 minutesToDie 시간(분)까지 기다려 죽는지 확인한다.

2. 돼지의 수를 저장할 pigs를 0으로 초기화한다.

3. $\frac{minutesToTest}{minutesToDie} + 1$를 pigs번 거듭 제곱한 결과가 buckets 미만일 때 까지 반복하여 pigs를 증가시킨다.
   • 양동이가 $5 \times 5$ 개의 경우, 두 마리의 돼지로 행, 열을 유추하여 독이 있는 양동이를 찾을 수 있다.
   • 양동이가 $5 \times 5 \times 5$ 개의 경우, 세 마리의 돼지로 행, 열, 높이를 유추하여 독이 있는 양동이를 찾을 수 있다.
   • 이런 방식으로 pigs를 증가시키고 이를 이용하여 거듭 제곱한 결과를 이용하여 $(\frac{minutesToTest}{minutesToDie} + 1)^{pigs}$개의 양동이를 처리할 수 있다.
4. 반복이 완료되면 돼지의 수인 pigs를 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.