λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

Algorithm

😊 ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€: Lv3. μž…κ΅­ 심사 (Java)

πŸ“Œ λ¬Έμ œ

nλͺ…이 μž…κ΅­μ‹¬μ‚¬λ₯Ό μœ„ν•΄ 쀄을 μ„œμ„œ 기닀리고 μžˆμŠ΅λ‹ˆλ‹€. 각 μž…κ΅­μ‹¬μ‚¬λŒ€μ— μžˆλŠ” μ‹¬μ‚¬κ΄€λ§ˆλ‹€ μ‹¬μ‚¬ν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ€ λ‹€λ¦…λ‹ˆλ‹€.

μ²˜μŒμ— λͺ¨λ“  μ‹¬μ‚¬λŒ€λŠ” λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€. ν•œ μ‹¬μ‚¬λŒ€μ—μ„œλŠ” λ™μ‹œμ— ν•œ λͺ…λ§Œ 심사λ₯Ό ν•  수 μžˆμŠ΅λ‹ˆλ‹€. κ°€μž₯ μ•žμ— μ„œ μžˆλŠ” μ‚¬λžŒμ€ λΉ„μ–΄ μžˆλŠ” μ‹¬μ‚¬λŒ€λ‘œ κ°€μ„œ 심사λ₯Ό 받을 수 μžˆμŠ΅λ‹ˆλ‹€. ν•˜μ§€λ§Œ 더 빨리 λλ‚˜λŠ” μ‹¬μ‚¬λŒ€κ°€ 있으면 κΈ°λ‹€λ Έλ‹€κ°€ 그곳으둜 κ°€μ„œ 심사λ₯Ό 받을 μˆ˜λ„ μžˆμŠ΅λ‹ˆλ‹€.

λͺ¨λ“  μ‚¬λžŒμ΄ 심사λ₯Ό λ°›λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ„ μ΅œμ†Œλ‘œ ν•˜κ³  μ‹ΆμŠ΅λ‹ˆλ‹€.

μž…κ΅­μ‹¬μ‚¬λ₯Ό κΈ°λ‹€λ¦¬λŠ” μ‚¬λžŒ 수 n, 각 심사관이 ν•œ λͺ…을 μ‹¬μ‚¬ν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ΄ λ‹΄κΈ΄ λ°°μ—΄ timesκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, λͺ¨λ“  μ‚¬λžŒμ΄ 심사λ₯Ό λ°›λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ˜ μ΅œμ†Ÿκ°’μ„ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μž‘μ„±ν•΄μ£Όμ„Έμš”.

πŸ“Œ μ œν•œμ‚¬ν•­

  • μž…κ΅­μ‹¬μ‚¬λ₯Ό κΈ°λ‹€λ¦¬λŠ” μ‚¬λžŒμ€ 1λͺ… 이상 1,000,000,000λͺ… μ΄ν•˜μž…λ‹ˆλ‹€.
  • 각 심사관이 ν•œ λͺ…을 μ‹¬μ‚¬ν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ€ 1λΆ„ 이상 1,000,000,000λΆ„ μ΄ν•˜μž…λ‹ˆλ‹€.
  • 심사관은 1λͺ… 이상 100,000λͺ… μ΄ν•˜μž…λ‹ˆλ‹€.

πŸ“Œ ν’€μ΄

μ œν•œμ‚¬ν•­μ„ 보면 μ΅œλŒ€ κΈ°λ‹€λ¦¬λŠ” μ‚¬λžŒμ€ 10μ–΅, 1λͺ…이 μ‹¬μ‚¬ν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ€ 10μ–΅λΆ„ μ΄ν•˜. λ‹¨μˆœ κ΅¬ν˜„μœΌλ‘œλŠ” μ‹œκ°„ 초과될 κ°€λŠ₯성이 맀우 λ†’λ‹€. μ–΄λ–»κ²Œ μ ‘κ·Όν•΄μ•Ό 할지 κ³ λ―Όν–ˆλ‹€. λͺ¨λ“  μ‚¬λžŒμ„ μ‹¬μ‚¬ν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ΅œλŒ€ μ‹œκ°„μœΌλ‘œ 이뢄 탐색을 ν•΄λ³΄μž.

μ‹¬μ‚¬ν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ΅œλŒ€ μ‹œκ°„ = 1λͺ… μ‹¬μ‚¬ν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ΅œλŒ€ μ‹œκ°„ x μ΅œλŒ€ 심사관 수
즉, 10μ–΅λΆ„ x 10만λͺ…μœΌλ‘œ 100μ‘°κ°€ λ‚˜μ˜¨λ‹€... (long νƒ€μž…μ€ 100μ‘° 컀버 κ°€λŠ₯)

min 값을 1, maxλ₯Ό 100쑰둜 두고 쀑간값(mid)을 전체 κ±Έλ¦¬λŠ” μ‹œκ°„(totalTime)으둜 κ°€μ •ν•œλ‹€. μ΄λ•Œ λͺ¨λ“  심사관이 totalTime λ™μ•ˆ λͺ‡λͺ…을 심사 ν•  수 μžˆλŠ”μ§€ 카운트 ν•œλ‹€. λ§Œμ•½μ— 심사λ₯Ό κΈ°λ‹€λ¦¬λŠ” μ‚¬λžŒ 수(n)보닀 ν¬κ±°λ‚˜ κ°™μœΌλ©΄, minκ³Ό mid 사이에 μ΅œμ†Œκ°’μ΄ μžˆλ‹€. λ§Œμ•½μ— μž‘λ‹€λ©΄, mid와 max 사이에 μ΅œμ†Œκ°’μ΄ μžˆλ‹€. 이λ₯Ό μ΄μš©ν•˜λ©΄ μ›ν•˜λŠ” κ²°κ³Όλ₯Ό 얻을 수 μžˆλ‹€.

μ‰½κ²Œ μ–˜κΈ°ν•˜μžλ©΄ 숫자 λ§žμΆ”κΈ° κ²Œμž„κ³Ό κ°™λ‹€. 1λΆ€ν„° 100κΉŒμ§€ μˆ«μžμ€‘μ— 홍길동이 μƒκ°ν•˜λŠ” 숫자λ₯Ό 맞좰보자. 1λΆ€ν„° 100κΉŒμ§€ μ–˜κΈ°ν•˜λ‹€λ³΄λ©΄ μ–Έμ  κ°„ λ‚˜μ˜¬ 것이닀. ν•˜μ§€λ§Œ λΉ„νš¨μœ¨μ μ΄μ§€ μ•Šμ€κ°€? λ‚΄κ°€ μ œμ‹œν•˜λŠ” μˆ«μžμ— λŒ€ν•΄μ„œ 홍길동은 ν¬κ±°λ‚˜ μž‘μ€μ§€λ§Œ μ–˜κΈ°ν•΄μ€€λ‹€κ³  ν•΄λ³΄μž. 그러면 μ•„λž˜μ™€ 같이 μ‰½κ²Œ 닡을 찾을 수 μžˆλ‹€.

홍길동이 μƒκ°ν•˜λŠ” 숫자: 70
50 -> 크닀. (50보닀 크고, 100보닀 μž‘λ‹€)
75 -> μž‘λ‹€. (50보닀 크고, 75보닀 μž‘λ‹€)
62 -> 크닀. (62보닀 크고, 75보닀 μž‘λ‹€)
68 -> 크닀. (68보닀 크고, 75보닀 μž‘λ‹€)
71 -> μž‘λ‹€. (68보닀 크고, 71보닀 μž‘λ‹€)
69 -> 크닀. (69보닀 크고, 71보닀 μž‘λ‹€) -> 70

μž…κ΅­ 심사 λ¬Έμ œλ„ 이와 같이 이뢄 탐색을 μ΄μš©ν•˜μ—¬ 짧은 μ½”λ“œλ‘œ ν•΄κ²°ν•  수 μžˆμ—ˆλ‹€.

πŸ“Œ μ½”λ“œ

public class μž…κ΅­μ‹¬μ‚¬ {

    @Test
    void test() {
        long solution = solution(6, new int[]{7, 10});
        assertThat(solution).isEqualTo(28);
    }

    public long solution(int n, int[] times) {
        long min = 1L;
        long max = 1_000_000_000L * 100_001L;

        while (min <= max) {
            long mid = (min + max) / 2;
            if (isBig(mid, times, n)) max = mid - 1L;
            else min = mid + 1L;
        }
        return min;
    }

    private boolean isBig(long totalTime, int[] times, int n) {
        long count = 0L;
        for (int time : times) {
            count += (totalTime / time);
        }
        return count >= n;
    }
}
 

ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€

μ½”λ“œ μ€‘μ‹¬μ˜ 개발자 μ±„μš©. μŠ€νƒ 기반의 ν¬μ§€μ…˜ 맀칭. ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€μ˜ 개발자 λ§žμΆ€ν˜• ν”„λ‘œν•„μ„ λ“±λ‘ν•˜κ³ , λ‚˜μ™€ 기술 ꢁ합이 잘 λ§žλŠ” 기업듀을 맀칭 λ°›μœΌμ„Έμš”.

programmers.co.kr