알고리즘/백준
15663번 N과M(9) 백준
글을 쓰는 개발자
2020. 12. 6. 19:36
반응형
문제: www.acmicpc.net/problem/15663
15663번: N과 M (9)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
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)
|
cs |
check는 해당하는 숫자가 총 몇 개인지 카운팅하는 배열이다.
passing 리스트는 현재 몇 개의 갯수가 있는지 확인하는 배열이다.
init은 처음에 중복되는 숫자가 나오지 않게 하기 위한 배열이다.
그리고 처음에 받은 li의 리스트 값을 집합에 넣은 다음 다시 리스트를 넣음으로써 중복제거를 하였다.
시간은 꽤 빠른 편에 속했지만 코드의 길이가 너무 길어서 다른 분들은 어떻게 했나 봤다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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()
|
cs |
참고:https://claude-u.tistory.com/311
#260 백준 파이썬 [15663] N과 M (9) - 순열
https://www.acmicpc.net/problem/15663 Solution 리스트에 먼저 permutation 함수를 이용해 전부를 추가해주고 중복된 항목만 걸러주면 된다. 비효율적이지만 쉬운 set() 집합 함수를 이용해서 중복을 걸러주었..
claude-u.tistory.com
이 분은 permutations라는 파이썬에서 제공하는 라이브러리로 해결하였다.
반응형