[pgs위장]list에 X를 추가하여 combinations 구하기
프로그래머스 위장
itertools.combinations
from itertools import combinations
순열과 조합, 확률 등을 공부할 때 나오는 조합을 구현하는 방법이다. ['headgear', 'eyewear', 'shoes']에서 2개를 뽑는다면, 3C2로 3가지의 경우가 발생할 것이다. combinations(list, 2)로 간단하게 구현할 수 있다.
아래 그림에서처럼 tuple형태로 두 개씩 짝지어진 데이터들이 itertools 형태로 담긴다. list에 담아주어야 계속 사용할 수 있다. 그렇지 않으면 한번 iter가 돌면 사라지기 때문
Question
모든 경우의 수를 세어 보는 문제이다.
Solution
Solution 1
PSEUDO
- count dict를 만든다.
ex) {'모자': 2가지, '신발': 3가지, '셔츠': 2가지} - key(의상 종류)를 가지고 combinations를 뽑는다. 모든 가능한 개수를 돌려본다.
ex) 3가지가 있다면 3C1, 3C2, 3C3 - 모든 콤비네이션에 대해 각 count 개수를 곱해준 값들을 뽑고, 이를 모두 더해서 답을 구한다.
ex) (모자,신발)이고 모자 2가지 신발 3가지가 있다면 이 콤비네이션은 2*3가지가 나올 수 있다는 뜻
from itertools import combinations as cbs
def sol_1(clothes):
# make dict
vocab = dict()
for name, cat in clothes:
if cat not in vocab:
vocab[cat] = 1
else:
vocab[cat] += 1
ans = 0
for num in range(1, len(vocab)+1):
for com in list(cbs(vocab, num)):
temp = 1
for c in com:
temp *= vocab[c]
ans += temp
return ans
Solution 2
접근 방식을 조금 다르게 하면 아주 간단하게 문제가 풀린다. 프로그래밍의 문제라기 보다는 사고력 테스트...
PSEUDO
- 똑같이 count dict를 만들고
- 각각의 count(value)에 +1 해준 후 다 곱해준다.
- 답은 이 값에서 -1 해주면 됨
왜? 아래처럼 생각해보자. 오른쪽처럼 X(입지 않는 경우)를 추가해주면 자연스럽게 hat과 shirt만 입는 경우, shoes만 입는 경우 등을 포함할 수 있다. (A, D, X), (X, X, G) 등으로. 그리고 마지막에 -1을 해주는 것은 모두 X가 선택되는 경우를 제거해줘야 하기 때문이다. 너무나 간단하게 O(n)으로 풀 수 있다.
def sol_2(clothes):
vocab = dict()
for name, cat in clothes:
if cat in vocab:
vocab[cat] += 1
else: vocab[cat] = 1
ans = 1
for i in vocab.values():
ans *= (i+1)
return ans-1
Solution 1은 한 개의 케이스에서 시간초과가 발생, 소요시간만 얼핏봐도 두 코드의 시간 효율 차이가 크다는 것을 알 수 있다. 시간초과가 나면 다르게 접근할 수 있도록 머리를 써야겠다..
Author And Source
이 문제에 관하여([pgs위장]list에 X를 추가하여 combinations 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jonas-jun/pgs-spy-combinations저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)