S3 15649. N과 M (1)

문제 보기 :  15649번: N과 M (1)

---

문제

• 정답률 : 63%

---

작성 코드

def per(n,new):
    global arr
    answer = []
    if len(new)==n:
        return [new]
    for i in range(len(arr)):
        if not visited[i]:
            visited[i]=True
            answer.extend(per(n,new+[arr[i]]))
            visited[i]=False
    return answer

n,m = map(int, input().split()) #1부터 n까지, m개
arr = [i for i in range(1,n+1)]
visited = [False]*n
k = per(m,[])

for i in k:
    print(*i, sep= ' ')

---

풀이

삼성 코딩 테스트는 itertools 사용이 안된다. 그래서 permutations, combinations 등등 순열과 조합을 모두 구현할 수 있어야하는데, 이 문제가 그 문제였다. 

하단에는 중복 순열, 조합, 중복 조합 코드도 추가해두겠다.

## 중복 순열

def product(n,new):
    global arr
    answer = []
    if len(new)==n:
        return [new]
    for i in range(len(arr)):
        answer.extend(product(n,new+[arr[i]]))
    return answer

## 조합

def combinations(n,new,c):
    answer = []
    if len(new)==n:
        return [new]
    for i in range(c,len(arr)):
        answer.extend(combinations(n,new+[arr[i]],i+1))
    return answer

## 중복 조합

def combinations(n,new,c):
    answer = []
    if len(new)==n:
        return [new]
    for i in range(c,len(arr)):
        answer.extend(combinations(n,new+[arr[i]],i+1))
    return answer

def combinations_with_replacements(n,new,c):
    answer = []
    if len(new)==n:
        return [new]
    for i in range(c,len(arr)):
        answer.extend(combinations(n,new+[arr[i]],i))
    return answer