[백준] 15651번 - N과 M (3)

참고: https://www.acmicpc.net/problem/15650

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

예제를 보아하니, 이번에는 앞선 문제 1과 2와는 다르게

중복한 수의 순열도 출력하는 것으로 보인다.

즉, 중복순열이라는 것이다.

 

itertools 라이브러리에서 permutations는 중복없는 순열을,

combinations는 중복없는 조합을 반환하는 함수였다.

그렇다면, 중복하는 순열과 조합은 어떻게 반환할까?

 

바로 product라는 함수를 통해 중복있는 순열을,

combinations_with_replacement라는 함수를 통해 중복있는 조합을

반환할 수가 있다.

 

n개에서 r를 뽑아야한다고 할 때,

 

1) product(반복 가능한 객체(n), repeat=반복할 수(r))

2) combinations_with_replacement(반복 가능한 객체(n), 뽑을 갯수(r))

3) permutations(n, r)

4) combinations(n, r)

 

다음과 같이 itertools 라이브러리의 함수를 사용할 수 있다.

 

import sys
from itertools import product
input = sys.stdin.readline

n, m = map(int, input().split())
data = list(product([i for i in range(1, n+1)], repeat=m))

for i in range(len(data)): print(*data[i])

 

문제에서 제시하는 바와 같이 사용한다면 다음 코드로 문제를 풀 수 있다.

하지만, 시간이 굉장히 오래 걸리는 것을 볼 수 있는데

이는 숫자를 계산하는 연산에서 오래 걸리게 되고,

숫자를 문자형으로 바꾸어 계산하면 빠르게 단축할 수 있게 된다.

 

import sys
from itertools import product
input = sys.stdin.readline

n, m = map(int, input().split())
data = map(str, range(1, n+1))

print('\n'.join(map(' '.join, product(data, repeat=m))))

 

map 객체에서 공백을 join하고, 줄바꿈을 join한 내용을

print 출력하게 되면, 이전보다 시간이 훨씬 단축된 것을 확인할 수 있다.

 

화이팅 💪