Skip to content

Latest commit

Β 

History

History
116 lines (86 loc) Β· 4.78 KB

2019-10-30-AT-spy.md

File metadata and controls

116 lines (86 loc) Β· 4.78 KB

2019λ…„ 10μ›” 30일

ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ - μœ„μž₯ (Hash) {docsify-ignore-all}

οΏ½

좜처: https://programmers.co.kr/learn/courses/30/lessons/42578

문제

μŠ€νŒŒμ΄λ“€μ€ 맀일 λ‹€λ₯Έ μ˜·μ„ μ‘°ν•©ν•˜μ—¬ μž…μ–΄ μžμ‹ μ„ μœ„μž₯ν•©λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄ μŠ€νŒŒμ΄κ°€ 가진 옷이 μ•„λž˜μ™€ κ°™κ³  였늘 μŠ€νŒŒμ΄κ°€ λ™κ·Έλž€ μ•ˆκ²½, κΈ΄ μ½”νŠΈ, νŒŒλž€μƒ‰ ν‹°μ…”μΈ λ₯Ό μž…μ—ˆλ‹€λ©΄ λ‹€μŒλ‚ μ€ 청바지λ₯Ό μΆ”κ°€λ‘œ μž…κ±°λ‚˜ λ™κ·Έλž€ μ•ˆκ²½ λŒ€μ‹  κ²€μ • μ„ κΈ€λΌμŠ€λ₯Ό μ°©μš©ν•˜κ±°λ‚˜ ν•΄μ•Ό ν•©λ‹ˆλ‹€.

μ’…λ₯˜ 이름
μ–Όκ΅΄ λ™κ·Έλž€ μ•ˆκ²½, κ²€μ • μ„ κΈ€λΌμŠ€
μƒμ˜ νŒŒλž€μƒ‰ ν‹°μ…”μΈ 
ν•˜μ˜ 청바지
κ²‰μ˜· κΈ΄ μ½”νŠΈ

μŠ€νŒŒμ΄κ°€ 가진 μ˜μƒλ“€μ΄ λ‹΄κΈ΄ 2차원 λ°°μ—΄ clothesκ°€ μ£Όμ–΄μ§ˆ λ•Œ μ„œλ‘œ λ‹€λ₯Έ 옷의 μ‘°ν•©μ˜ 수λ₯Ό return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μž‘μ„±ν•΄μ£Όμ„Έμš”.

μ œν•œμ‚¬ν•­

  • clothes의 각 행은 [μ˜μƒμ˜ 이름, μ˜μƒμ˜ μ’…λ₯˜]둜 이루어져 μžˆμŠ΅λ‹ˆλ‹€.
  • μŠ€νŒŒμ΄κ°€ 가진 μ˜μƒμ˜ μˆ˜λŠ” 1개 이상 30개 μ΄ν•˜μž…λ‹ˆλ‹€.
  • 같은 이름을 가진 μ˜μƒμ€ μ‘΄μž¬ν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.
  • clothes의 λͺ¨λ“  μ›μ†ŒλŠ” λ¬Έμžμ—΄λ‘œ 이루어져 μžˆμŠ΅λ‹ˆλ‹€.
  • λͺ¨λ“  λ¬Έμžμ—΄μ˜ κΈΈμ΄λŠ” 1 이상 20 μ΄ν•˜μΈ μžμ—°μˆ˜μ΄κ³  μ•ŒνŒŒλ²³ μ†Œλ¬Έμž λ˜λŠ” '_' 둜만 이루어져 μžˆμŠ΅λ‹ˆλ‹€.
  • μŠ€νŒŒμ΄λŠ” ν•˜λ£¨μ— μ΅œμ†Œ ν•œ 개의 μ˜μƒμ€ μž…μŠ΅λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

clothes return
[['yellow_hat', 'headgear'], ['blue_sunglasses', 'eyewear'], ['green_turban', 'headgear']] 5
[['crow_mask', 'face'], ['blue_sunglasses', 'face'], ['smoky_makeup', 'face']] 3

μ ‘κ·Ό 방법

  • κ²°κ΅­ μ˜μƒ μ’…λ₯˜λ³„ 옷의 갯수의 쑰합을 κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€.

    • 단, 같은 μ’…λ₯˜μ˜ μ˜·μ„ κ³ λ₯Ό μˆ˜λŠ” μ—†λ‹€.
  • λ¬Έμ œμ—μ„œ 같은 이름을 가진 μ˜μƒμ€ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ”λ‹€ λΌλŠ” 쑰건이 μžˆλ‹€.

    • λ”°λΌμ„œ μ˜μƒ 이름은 μ‹ κ²½ μ•ˆμ¨λ„ λœλ‹€.
    • ν•΄λ‹Ή μ˜μƒμ΄ λͺ‡ κ°œμΈμ§€λ§Œ μ•Œλ©΄λ˜λ―€λ‘œ μ˜μƒ μ’…λ₯˜κ°€ λ‚˜μ˜¨ 횟수λ₯Ό 톡해 μ˜μƒ 갯수λ₯Ό κ΅¬ν•œλ‹€.
    • μ˜μƒ μ’…λ₯˜λ₯Ό key κ°’μœΌλ‘œν•˜κ³  μ˜μƒ μ’…λ₯˜κ°€ λ‚˜μ˜¨ 횟수λ₯Ό value둜 ν•˜λŠ” HashMap을 λ§Œλ“€λ©΄ λœλ‹€.
  • μ—¬κΈ°κΉŒμ§€λŠ” μ‰¬μš΄λ° λ¬Έμ œλŠ” μ˜μƒ μ’…λ₯˜λ³„λ‘œ ν•˜λ‚˜μ”© μ„ νƒν•˜λŠ” 방법이닀.

  • λ‚΄κ°€ μ‹œλ„ν•œ λ°©λ²•μ—μ„œλŠ” μ‹œκ°„ μ΄ˆκ³Όκ°€ λ‚˜μ„œ λ‹€λ₯Έ μ‚¬λžŒμ˜ 풀이λ₯Ό μ°Έκ³ ν–ˆλ‹€.

  • 핡심은 (Aμ’…λ₯˜ 옷 κ°€μ§€μˆ˜ + 1)*(Bμ’…λ₯˜ 옷 κ°€μ§€μˆ˜ + 1)*(Cμ’…λ₯˜ 옷 κ°€μ§€μˆ˜ + 1) - 1 이닀.

  • 예λ₯Ό λ“€μ–΄

    • μƒμ˜λ‘œ a, b, c λΌλŠ” μ΄λ¦„μ˜ 3κ°œκ°€ μžˆλ‹€.
    • ν•˜μ˜λ‘œ e, f λΌλŠ” μ΄λ¦„μ˜ 2κ°œκ°€ μžˆλ‹€.
    • 이 경우, μ’…λ₯˜ λ‹Ή ν•˜λ‚˜μ”© μ˜·μ„ μ„ νƒν•˜λŠ” μ‘°ν•©ν•˜λŠ” 방법은
    • (0,a,b,c) * (0,e,f) 이닀. (0은 아무것도 κ³ λ₯΄μ§€ μ•Šμ€ κ²½μš°μ΄λ‹€.)
    • λ¬Έμ œμ—μ„œ μ΅œμ†Œ ν•œ 개의 μ˜μƒμ€ μž…μŠ΅λ‹ˆλ‹€.λΌλŠ” 쑰건이 μžˆμœΌλ―€λ‘œ λ‘˜ λ‹€ κ³ λ₯΄μ§€ μ•Šμ€ 경우(0,0)λŠ” λΉΌμ•Όν•œλ‹€.
    • λ”°λΌμ„œ 4*3-1 이 μ΅œμ’… 경우의 μˆ˜κ°€ λœλ‹€.

λ‚΄ 풀이1

μ‹œκ°„ 초과

  • μ˜μƒ μ’…λ₯˜λ³„ 옷의 갯수λ₯Ό κ΅¬ν•˜λŠ” 과정을 μ–΄λ–»κ²Œ 해야할지 λͺ°λΌμ„œ combinations λͺ¨λ“ˆμ„ μ΄μš©ν•΄μ„œ κ΅¬ν–ˆλ‹€. μ΄λ ‡κ²Œ ν•˜λ‹ˆ ν…ŒμŠ€νŠΈμΌ€μ΄μŠ€ 쀑 ν•˜λ‚˜λ₯Ό μ‹œκ°„μ΄ˆκ³Όλ‘œ ν†΅κ³Όν•˜μ§€ λͺ»ν–ˆλ‹€.

  • μ•Œκ³ λ¦¬μ¦˜ 문제λ₯Ό ν’€ λ•Œ combinationsλ₯Ό μ“°λ©΄ 거의 μ‹œκ°„μ΄ˆκ³Όκ°€ λ‚œλ‹€. μ“°λ©΄ μ•ˆ λ˜λŠ”κ±Έ μ•Œλ©΄μ„œλ„ κΈ‰ν• λ•ŒλŠ” μ“°κ²Œ λœλ‹€. κ²°κ΅­ 틀릴 κ±Έ μ•Œλ©΄μ„œλ„..

from itertools import combinations
import numpy

def solution(clothes):
    s = set()
    d = dict()
    for i in range(len(clothes)):
        if clothes[i][1] not in s:
            s.add(clothes[i][1])
            d[clothes[i][1]] = 1
        else:
            d[clothes[i][1]] += 1
    answer = []
    for j in range(1, len(d)+1):
        answer.append(list(combinations(d.values(), j)))
    p = 0
    for k in answer:
        for i in k:
            p +=numpy.prod(i)
    return p

λ‚΄ 풀이2

  • (Aμ’…λ₯˜ 옷 κ°€μ§€μˆ˜ + 1)*(Bμ’…λ₯˜ 옷 κ°€μ§€μˆ˜ + 1)*(Cμ’…λ₯˜ 옷 κ°€μ§€μˆ˜ + 1) - 1 λΌλŠ” 방식을 μ•Œκ³ λ‚˜λ‹ˆ κ°„λ‹¨νžˆ ν’€ 수 μžˆμ—ˆλ‹€.
def solution(clothes):
    d = dict()
    for i in range(len(clothes)):
        if d.get(clothes[i][1]) is None:
            d[clothes[i][1]] = 1
        else:
            d[clothes[i][1]] += 1
    answer = 1
    print(d.values())
    for j in d.values():
        answer *= (j+1)

    return answer-1

배운점

  • λ°°μ—΄ A,B,Cμ—μ„œ λ°°μ—΄ λ‹Ή μš”μ†Œ ν•˜λ‚˜μ”© μ„ νƒν•˜λŠ” λͺ¨λ“  쑰합을 κ΅¬ν•˜λŠ” 경우의 μˆ˜λŠ” (A+1) * (B+1) * (C+1) 이닀.