15663번 N과M(9) 백준

문제: www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

import sys
N,M = map(int,sys.stdin.readline().split())
li=[int(i) for i in sys.stdin.readline().split()]
check=[0]*10001
passing=[0]*10001
init=[False]*10001
for i in li:
    check[i]+=1
dic = set(li)
li=list(dic)
li.sort()
ans=[]
 
def func(celi):
    if celi==M:
        print(' '.join(ans))
        return
    for i in range(len(li)):
        if not ans:
            if init[li[i]]!=True:
                init[li[i]]=True
                passing[li[i]]=1
                ans.append(str(li[i]))
                func(celi+1)
                passing[li[i]]=0
                ans.pop()
        else:
            if passing[li[i]]<check[li[i]]:
                passing[li[i]]+=1
                ans.append(str(li[i]))
                func(celi+1)
                passing[li[i]]-=1
                ans.pop()
 
func(0)

check는 해당하는 숫자가 총 몇 개인지 카운팅하는 배열이다. 

passing 리스트는 현재 몇 개의 갯수가 있는지 확인하는 배열이다.

init은 처음에 중복되는 숫자가 나오지 않게 하기 위한 배열이다.

그리고 처음에 받은 li의 리스트 값을 집합에 넣은 다음 다시 리스트를 넣음으로써 중복제거를 하였다.

 

시간은 꽤 빠른 편에 속했지만 코드의 길이가 너무 길어서 다른 분들은 어떻게 했나 봤다.

 

 

from itertools import permutations
 
N, M = map(int, input().split())
N_list = list(map(int, input().split()))
N_list = sorted(N_list) #순서대로 나오게 정렬 먼저
 
output = []
for numbers in list(permutations(N_list, M)):
    output.append(numbers)
output = sorted(list(set(output))) #중복 제거 후 정렬 까지 한번에!
 
for numbers in output:
    for num in numbers:
        print(num, end=' ')
    print()

참고:https://claude-u.tistory.com/311

#260 백준 파이썬 [15663] N과 M (9) - 순열

이 분은 permutations라는 파이썬에서 제공하는 라이브러리로 해결하였다.