Chapter11. μμ£Ό λ±μ₯νλ μλ£ κ΅¬μ‘°
[λ¬Έμ 49] 보μ μΌν - Level3
κ°λ°μ μΆμ μΌλ‘ μΈκ³ μ΅κ³ μ κ°λΆκ° λ μ΄νΌμΉλ μ€νΈλ μ€λ₯Ό λ°μ λλ©΄ μ΄λ₯Ό νκΈ° μν΄ μ€νλΌμΈ 맀μ₯μ μΌνμ νλ¬ κ°κ³€ ν©λλ€.
μ΄νΌμΉλ μΌνμ ν λλ©΄ 맀μ₯ μ§μ΄λμ νΉμ λ²μμ 물건λ€μ λͺ¨λ μΉμΈμ΄ ꡬ맀νλ μ΅κ΄μ΄ μμ΅λλ€.
μ΄λ λ μ€νΈλ μ€λ₯Ό νκΈ° μν΄ λ³΄μ 맀μ₯μ μΌνμ νλ¬ κ° μ΄νΌμΉλ μ΄μ μ²λΌ μ§μ΄λμ νΉμ λ²μμ 보μμ λͺ¨λ ꡬ맀νλ νΉλ³ν μλ λͺ©μ μ λ¬μ±νκ³ μΆμμ΅λλ€.
- 'μ§μ΄λ λͺ¨λ μ’
λ₯μ 보μμ μ μ΄λ 1κ° μ΄μ ν¬ν¨νλ κ°μ₯ 짧μ ꡬκ°μ μ°Ύμμ ꡬ맀'
μλ₯Ό λ€μ΄ μλ μ§μ΄λλ 4μ’
λ₯μ 보μ(RUBY, DIA, EMERALD, SAPPHIRE) 8κ°κ° μ§μ΄λ μμμ
λλ€.
μ§μ΄λ λ²νΈ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|
보μ μ΄λ¦ | DIA | RUBY | RUBY | DIA | DIA | EMERALD | SAPPHIRE | DIA |
μ§μ΄λμ 3λ²λΆν° 7λ²κΉμ§ 5κ°μ 보μμ ꡬ맀νλ©΄ λͺ¨λ μ’
λ₯μ 보μμ μ μ΄λ νλ μ΄μμ© ν¬ν¨νκ² λ©λλ€.
μ§μ΄λμ 3, 4, 6, 7λ²μ 보μλ§ κ΅¬λ§€νλ κ²μ μ€κ°μ νΉμ ꡬκ°(5λ²)μ΄ λΉ μ§κ² λλ―λ‘ μ΄νΌμΉμ μΌν μ΅κ΄μ λ§μ§ μμ΅λλ€.
μ§μ΄λ λ²νΈ μμλλ‘ λ³΄μλ€μ μ΄λ¦μ΄ μ μ₯λ λ°°μ΄ gemsκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§λλ€. μ΄λ λͺ¨λ 보μμ νλ μ΄μ ν¬ν¨νλ κ°μ₯ 짧μ ꡬκ°μ μ°Ύμμ returnνλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
κ°μ₯ 짧μ ꡬκ°μ μμ μ§μ΄λ λ²νΈμ λ μ§μ΄λ λ²νΈλ₯Ό μ°¨λ‘λλ‘ λ°°μ΄μ λ΄μμ return νλλ‘ νλ©°, λ§μ½ κ°μ₯ 짧μ ꡬκ°μ΄ μ¬λ¬ κ°λΌλ©΄ μμ μ§μ΄λ λ²νΈκ° κ°μ₯ μμ ꡬκ°μ returnν©λλ€.
[μ νμ¬ν]
- gems λ°°μ΄μ ν¬κΈ°λ 1 μ΄μ 100,000 μ΄νμ
λλ€.
- gems λ°°μ΄μ κ° μμλ μ§μ΄λμ λμ΄λ 보μμ λνλ
λλ€.
- gems λ°°μ΄μλ 1λ² μ§μ΄λλΆν° μ§μ΄λ λ²νΈ μμλλ‘ λ³΄μ μ΄λ¦μ΄ μ°¨λ‘λλ‘ μ μ₯λμ΄ μμ΅λλ€.
- gems λ°°μ΄μ κ° μμλ κΈΈμ΄κ° 1 μ΄μ 10 μ΄νμΈ μνλ²³ λλ¬Έμλ‘λ§ κ΅¬μ±λ λ¬Έμμ΄μ
λλ€.
[μ½λμμ±]
1. 보μμ μ’
λ₯μ νμ¬ κ°μ§κ³ μλ 보μμ μ μ
def solution(gems):
kind = len(set(gems))
size = len(gems)
answer = [0, size - 1]
dic = {gems[0]:1}
start = end = 0
2. μμ ν¬μΈν°λΆν° λ ν¬μΈν°κΉμ§ μ λΆ κ΅¬λ§€νλ€κ³ νμ λ λͺ¨λ μ’
λ₯μ 보μμ μ΄ μ μλμ§ νμΈ
while end < size:
if len(dic) < kind:
end += 1
if end == size: break
dic[gems[end]] = dic.get(gems[end], 0) + 1
else:
if (end - start + 1) < (answer[1] - answer[0] + 1): answer = [start, end]
if dic[gems[start]] == 1: del dic[gems[start]]
else: dic[gems[start]] -= 1
start += 1
3. ꡬκ°μ 보μ νκ³ μ λ΅μ λ°ν
answer[0] += 1
answer[1] += 1
return answer
[μ 체μ½λ]
def solution(gems):
kind = len(set(gems))
size = len(gems)
answer = [0, size - 1]
dic = {gems[0]:1}
start = end = 0
while end < size:
if len(dic) < kind:
end += 1
if end == size: break
dic[gems[end]] = dic.get(gems[end], 0) + 1
else:
if (end - start + 1) < (answer[1] - answer[0] + 1): answer = [start, end]
if dic[gems[start]] == 1: del dic[gems[start]]
else: dic[gems[start]] -= 1
start += 1
answer[0] += 1
answer[1] += 1
return answer