[BOJ] N과 M (10) 15664 R

출처:: https://www.acmicpc.net/problem/15664

 

1. 문제 이해 및 해결과정

-중복되는 경우의 수를 제외한 조합

 

2. 풀이방법

 1.조합 라이브러리

#N과 M (10)
#https://www.acmicpc.net/problem/15664
import sys
import itertools as it
sys.stdin = open("input.txt","r")

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for k in sorted(set(it.combinations(a,m))):
    #print(k)
    print(' '.join(map(str,k)))

 2. 각 수의 개수를 이용하는 방법, DFS

#N과 M (10) 2
#https://www.acmicpc.net/problem/15664
import sys
from collections import Counter
sys.stdin = open("input.txt","r")

def DFS(L,s):
    if L==m:
        for x in res:
            print(x,end=' ')
        print()
    else:
        for i in range(s,len(cnt)):
            if cnt[i]:
                res[L]=num[i]
                cnt[i]-=1
                DFS(L+1,i)
                cnt[i]+=1

if __name__=="__main__":
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    num, cnt = map(list, zip(*list(Counter(a).items())))
    res=[0]*m
    DFS(0,0)

3. 오답원인

 

4. 알게된 점

zip(*iterable)

: 동일한 개수로 이루어진 자료형을 묶어 주는 역할을 하는 함수

 

counter()

from collections import Counter

Counter('hello') # Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1})

 

num, cnt = map(list, zip(*list(Counter(a).items())))

: 이 코드가 숫자 별 개수 를 각각 세서 만들어주는 코드이다.

num, cnt 이용하기

결과는 이와 같다. 

c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs

print(Counter(a).items()) ##dict_items([(1, 2), (2, 2)])
print(list(Counter(a).items())) ##[(1, 2), (2, 2)]
print(zip(*list(Counter(a).items()))) ##<zip object at 0x020DB6C8>