Chapter8. μ΄μ§ νμ
[λ¬Έμ 32] μ§κ²λ€λ¦¬ 건λκΈ° - Level3
μΉ΄μΉ΄μ€ μ΄λ±νκ΅μ 'λλμ¦ μΉκ΅¬λ€'μ΄ 'λΌμ΄μΈ' μ μλκ³Ό ν¨κ» κ°μ μνμ κ°λ μ€μ μ§κ²λ€λ¦¬κ° μλ κ°μΈμ λ§λμ 건λνΈμΌλ‘ 건λλ €κ³ ν©λλ€. 'λΌμ΄μΈ' μ μλμ 'λλμ¦ μΉκ΅¬λ€'μ΄ λ¬΄μ¬ν μ§κ²λ€λ¦¬λ₯Ό 건λ μ μλλ‘ λ€μκ³Ό κ°μ΄ κ·μΉμ λ§λ€μμ΅λλ€.
- μ§κ²λ€λ¦¬λ μΌλ ¬λ‘ λμ¬ μκ³ κ° μ§κ²λ€λ¦¬μ λλ€λμλ λͺ¨λ μ«μκ° μ ν μμΌλ©° λλ€λμ μ«μλ ν λ² λ°μ λλ§λ€ 1μ© μ€μ΄λλλ€.
- λλ€λμ μ«μκ° 0μ΄ λλ©΄ λ μ΄μ λ°μ μ μμΌλ©° μ΄λλ κ·Έλ€μ λλ€λλ‘ ν λ²μ μ¬λ¬ μΉΈμ 건λλΈ μ μμ΅λλ€.
- λ¨, λ€μμΌλ‘ λ°μ μ μλ λλ€λμ΄ μ¬λ¬ κ°μΈ κ²½μ° λ¬΄μ‘°κ±΄ κ°μ₯ κ°κΉμ΄ λλ€λλ‘λ§ κ±΄λλΈ μ μμ΅λλ€.
'λλμ¦ μΉκ΅¬λ€'μ κ°μΈμ μΌμͺ½μ μμΌλ©°, κ°μΈμ μ€λ₯Έμͺ½ 건λνΈμ λμ°©ν΄μΌ μ§κ²λ€λ¦¬λ₯Ό 건λ κ²μΌλ‘ μΈμ ν©λλ€.
'λλμ¦ μΉκ΅¬λ€'μ ν λ²μ ν λͺ
μ© μ§κ²λ€λ¦¬λ₯Ό 건λμΌ νλ©°, ν μΉκ΅¬κ° μ§κ²λ€λ¦¬λ₯Ό λͺ¨λ 건λ νμ κ·Έλ€μ μΉκ΅¬κ° 건λκΈ° μμν©λλ€.
λλ€λμ μ ν μ«μκ° μμλλ‘ λ΄κΈ΄ λ°°μ΄ stonesμ ν λ²μ 건λλΈ μ μλ λλ€λμ μ΅λ μΉΈ μ kκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μ΅λ λͺ λͺ
κΉμ§ μ§κ²λ€λ¦¬λ₯Ό 건λ μ μλμ§ returnνλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
[μ νμ¬ν]
- μ§κ²λ€λ¦¬λ₯Ό 건λμΌ νλ 'λλμ¦ μΉκ΅¬λ€'μ μλ 무μ νμ΄λΌκ³ κ°μ£Ό
- stones λ°°μ΄μ ν¬κΈ°λ 1 μ΄μ 200,000 μ΄ν
- stones λ°°μ΄ κ° μμλ€μ κ°μ 1 μ΄μ 200,000,000 μ΄νμΈ μμ°μ
- kλ 1 μ΄μ stonesμ κΈΈμ΄ μ΄νμΈ μμ°μ
[λ¬Έμ νμ΄]
- μ²μμ 0, λμ λλ€λ μ€ κ°μ₯ ν° μ«μλ₯Ό μ§μ
- νμ¬ μ£Όμ΄μ§ μΈμ μλ§νΌ λ€λ¦¬λ₯Ό 건λ μ μλμ§λ₯Ό νλ¨νλ ν¨μλ§λ€κΈ°
- ν¨μμ κ²°κ΄κ°μ λ°λΌ μ΄μ§ νμ μν
[μ½λμμ±]
- μ²μμ 0, λμ λλ€λ μ€ κ°μ₯ ν° μ«μλ₯Ό μ§μ
def solution(stones, k):
start, end = 0, max(stones)
answer = 0
- νμ¬ μ£Όμ΄μ§ μΈμ μλ§νΌ λ€λ¦¬λ₯Ό 건λ μ μλμ§λ₯Ό νλ¨νλ ν¨μλ§λ€κΈ°
def available(n, stones, k):
skip = 0
for stone in stones:
if stone < n:
skip += 1
if skip >= k: return False
else: skip = 0
return True
- ν¨μμ κ²°κ΄κ°μ λ°λΌ μ΄μ§ νμ μν
while start <= end:
mid = (start + end) // 2
if available(mid, stones, k):
start = mid + 1
answer = max(answer, mid)
else: end = mid - 1
return answer
[μ 체μ½λ]
def available(n, stones, k):
skip = 0
for stone in stones:
if stone < n:
skip += 1
if skip >= k: return False
else: skip = 0
return True
def solution(stones, k):
start, end = 0, max(stones)
answer = 0
while start <= end:
mid = (start + end) // 2
if available(mid, stones, k):
start = mid + 1
answer = max(answer, mid)
else: end = mid - 1
return answer
[λ€λ₯Έ νμ΄]
- 미리 λμ
λ리 λ°μ΄ν°λ₯Ό λ§λ€μ΄λμ λ³μ μ μΈ
from collections import defaultdict
def solution(info, query):
answer = []
people = defaultdict(list)
- μ£Όμ΄μ§ λͺ¨λ μ§μμμ λ°μ΄ν°λ₯Ό for λ¬ΈμΌλ‘ μννλ©΄μ κ°λ₯ν κ²½μ°μ μλ₯Ό λμ
λ리μ κΈ°λ‘
from itertools import combinations
for i in info:
person = i.split()
score = int(person.pop())
people[''.join(person)].append(score)
for j in range(4):
case = list(combinations(person, j))
for c in case:
people[''.join(c)].append(score)
- κΈ°λ‘ν λμ
λ리μ μ±μ λ°μ΄ν°λ₯Ό λͺ¨λ μ λ ¬
for i in people: people[i].sort()
- λ¬Έμ 쑰건μ λ°λΌ κ²μνκ³ , λμ¨ κ²°κ³Όμ μ±μ λ°°μ΄μ μ΄μ§ νμνμ¬ λͺ λͺ
μΈμ§ νμΈ
from bisect import bisect_left as left_bound
for i in query:
key = i.split()
score = int(key.pop())
key = ''.join(key)
key = key.replce('and', '').replace(' ', '').replace('-', '')
answer.append(len(people[key]) - left_bound(people[key], score))
return answer
[μ 체μ½λ]
from itertools import combinations
from collections import defaultdict
from bisect import bisect_left as left_bound
def solution(info, query):
answer = []
people = defaultdict(list)
for i in info:
person = i.split()
score = int(person.pop())
people[''.join(person)].append(score)
for j in range(4):
case = list(combinations(person, j))
for c in case:
people[''.join(c)].append(score)
for i in people: people[i].sort()
for i in query:
key = i.split()
score = int(key.pop())
key = ''.join(key)
key = key.replce('and', '').replace(' ', '').replace('-', '')
answer.append(len(people[key]) - left_bound(people[key], score))
return answer