Notice
Recent Posts
Recent Comments
ยซ   2025/04   ยป
์ผ ์›” ํ™” ์ˆ˜ ๋ชฉ ๊ธˆ ํ† 
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
Tags more
Archives
Today
Total
๊ด€๋ฆฌ ๋ฉ”๋‰ด

๐ŸŒฒ์ž๋ผ๋‚˜๋Š”์ฒญ๋…„

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ž…๊ตญ์‹ฌ์‚ฌ,python ๋ณธ๋ฌธ

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ž…๊ตญ์‹ฌ์‚ฌ,python

JihyunLee 2021. 2. 2. 13:33
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ์„ค๋ช…

programmers.co.kr/learn/courses/30/lessons/43238

n๋ช…์ด ์ž…๊ตญ์‹ฌ์‚ฌ๋ฅผ ์œ„ํ•ด ์ค„์„ ์„œ์„œ ๊ธฐ๋‹ค๋ฆฌ๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ์ž…๊ตญ์‹ฌ์‚ฌ๋Œ€์— ์žˆ๋Š” ์‹ฌ์‚ฌ๊ด€๋งˆ๋‹ค ์‹ฌ์‚ฌํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์€ ๋‹ค๋ฆ…๋‹ˆ๋‹ค.
์ฒ˜์Œ์— ๋ชจ๋“  ์‹ฌ์‚ฌ๋Œ€๋Š” ๋น„์–ด์žˆ์Šต๋‹ˆ๋‹ค. ํ•œ ์‹ฌ์‚ฌ๋Œ€์—์„œ๋Š” ๋™์‹œ์— ํ•œ ๋ช…๋งŒ ์‹ฌ์‚ฌ๋ฅผ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ€์žฅ ์•ž์— ์„œ ์žˆ๋Š” ์‚ฌ๋žŒ์€ ๋น„์–ด ์žˆ๋Š” ์‹ฌ์‚ฌ๋Œ€๋กœ ๊ฐ€์„œ ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ ๋” ๋นจ๋ฆฌ ๋๋‚˜๋Š” ์‹ฌ์‚ฌ๋Œ€๊ฐ€ ์žˆ์œผ๋ฉด ๊ธฐ๋‹ค๋ ธ๋‹ค๊ฐ€ ๊ทธ๊ณณ์œผ๋กœ ๊ฐ€์„œ ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›์„ ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.
๋ชจ๋“  ์‚ฌ๋žŒ์ด ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ์ตœ์†Œ๋กœ ํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.
์ž…๊ตญ์‹ฌ์‚ฌ๋ฅผ ๊ธฐ๋‹ค๋ฆฌ๋Š” ์‚ฌ๋žŒ ์ˆ˜ n, ๊ฐ ์‹ฌ์‚ฌ๊ด€์ด ํ•œ ๋ช…์„ ์‹ฌ์‚ฌํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์ด ๋‹ด๊ธด ๋ฐฐ์—ด times๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์‚ฌ๋žŒ์ด ์‹ฌ์‚ฌ๋ฅผ ๋ฐ›๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์˜ ์ตœ์†Ÿ๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

ํ’€์ด

์ฒ˜์Œ์—๋Š” for ๋ฌธ์œผ๋กœ ์ง์ ‘ ์‹œ๊ฐ„์„ ์ฐพ๋Š” ๋ฐฉ์‹์œผ๋กœ ํ’€์—ˆ๋Š”๋ฐ, time out์œผ๋กœ ๋ฌธ์ œ๋ฅผ ์ œ๋Œ€๋กœ ํ•ด๊ฒฐํ•˜์ง€ ๋ชปํ–ˆ๋‹ค.

๊ทธ๋ž˜์„œ ๋‹ค๋ฅธ ์‚ฌ๋žŒ๋“ค์˜ ํ’€์ด๋ฅผ ์ฐพ์•„์„œ ์ด๋ถ„ํƒ์ƒ‰์œผ๋กœ ํ’€์–ด๋ณด์•˜๋‹ค. 

๊ฒ€์‚ฌ์— ๊ฑธ๋ฆฌ๋Š” ์ด ์‹œ๊ฐ„์„ left right๋กœ ๋‘๊ณ , ๊ทธ ์‹œ๊ฐ„ ์•ˆ์—์„œ ์ตœ์ ์˜ ์‹œ๊ฐ„์„ ์ฐพ์•„๋‚˜๊ฐ€๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ’€์–ด๋ณด์•˜๋‹ค.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
def solution(n, times):
    ## 0 ~ ์ตœ์•…์˜ ์‹œ๊ฐ„๊นŒ์ง€ ํƒ์ƒ‰
    left , right = 0, max(times) * n
    answer =0
    while left <= right:
        mid = (left + right) //2
        ## ๊ฐ ์‹ฌ์‚ฌ๊ด€์€ ์ด ์‹œ๊ฐ„๋™์•ˆ ์ด ๋ช‡๋ช…์„ ๋ฐ›์„ ์ˆ˜ ์žˆ์„๊นŒ?
        people = 0
        for inspector in times:
            people += (mid//inspector)
            
            if people >= n:
                break
        ## ์‹œ๊ฐ„๋‚ด์— ๋‹ค ๋ฐ›์„ ์ˆ˜ ์žˆ์—ˆ์œผ๋ฉด, ๊ฐ’์„ ํ• ๋‹นํ•˜๊ณ  ๋ฒ”์œ„๋ฅผ ์ค„์ธ๋‹ค
        if people>=n:
            right = mid-1
            answer = mid
        ## ์‹œ๊ฐ„๋‚ด์— ๋‹ค ๋ฐ›์ง€ ๋ชปํ–ˆ์œผ๋ฉด, ์‹œ๊ฐ„์„ ๋Š˜๋ฆฐ๋‹ค
        else:
            left = mid+1
            
    return  answer
cs
๋ฐ˜์‘ํ˜•