수열 문제 N과 M

N과 M (1)

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

512 MB

38758

23619

15846

60.363%

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력

3 1

출력

1

2

3

예제  입력 

4 2

출력

1 2

1 3

1 4

2 1

2 3

2 4

3 1

3 2

3 4

4 1

4 2

4 3

 

우선 위 문제는 숫자 순서대로 출력을 출력을 진행해야하며 순서가 바뀌거나 서로 겹치면 안되는 문제이다. 즉 permutation(순열)을 사용해서 풀어야 하는 문제이다. 

 

 라이브러리를 사용해서 푸는 방법 

 

일단 아래는 python 에서 제공하는 라이브러리를 사용해서 푸는 방법이다. 

from itertools import permutations

n = [1,2,3,4]
k = 2

list(permutations( n,k ))
'''
[(1, 2),
 (1, 3),
 (1, 4),
 (2, 1),
 (2, 3),
 (2, 4),
 (3, 1),
 (3, 2),
 (3, 4),
 (4, 1),
 (4, 2),
 (4, 3)]
'''

 

 

 함수형 프로그래밍을 사용해 푸는 방법 

def permutation (numbers) :
    if len(numbers) <= 1 :
        return [numbers]
    
    result = []
    for i, num in enumerate( numbers ) :
        Temp = numbers.copy() 
        del Temp[i]
        rest = permutation(Temp)
        result.extend(list(map( lambda x : [num, *x], rest )) )

    return result

이제 다음으로 함수형 프로그래밍을 사용해서 풀어보자, 우리는 저번 시간에 permutation을 만드는 방법을 배웠다. 

근데 이렇게만 두면 더 특정 갯수의 순열은 구하기는 힘들어 진다. 여기서 함수를 조금 손봐서 정해진 갯수의 순열을 구하도록 한다. 

 

def permutation (numbers, count = 1) :
    if len(numbers) <= count :
        return [[numbers[0]]]
    
    result = []
    for i, num in enumerate( numbers ) :
        Temp = numbers.copy() 
        del Temp[i]
        rest = permutation(Temp, count)
        result.extend( map( lambda x : [num, *x], rest ) ) 

    return result

코드를 조금 수정하였다. count 보다 숫자가 작거나 같아 졌을때 멈추도록 하여 순열을 자신의 갯수에 맞추도록 한다. 

이제 완성된 코드를 살펴 보자. 

def permutation (numbers, count = 1) :
    if len(numbers) <= count :
        return [[numbers[0]]]
    
    result = []
    for i, num in enumerate( numbers ) :
        Temp = numbers.copy() 
        del Temp[i]
        rest = permutation(Temp, count)
        result.extend( map( lambda x : [num, *x], rest ) ) 

    return result 


a = [1,2,3,4]
k = 2
# 길이가 2개 인 순열을 만든다면 len(a) - k를 하여 이 아상 숫자가 커지지 않게한다. 
count = ( len(a) - k ) if ( len(a) - k  ) else 1
result = (permutation(a, count))

for _r in result :
    print(_r[:k])

이 코드를 보면

1. count = ( len(a) - k ) if ( len(a) - k  ) else 1
2. for _r in result :
       print(_r[:k])

이 2부분이 조금 이해가 되지 않을 것이다. 우선 count를 왜 다음과 같이 표현을 하였냐면 순열 nPr과 nPr-1의 가지수는 똑같이 나오게 되어 있다. 위 식에서 단순히 2개의 순열을 뽑는다고 하여 길이가 4인 행렬에서 2를 빼고 숫자 1을 더한 3을 count에 넣게 되면 count 3보다 작거나 같은때의 조건문이 만들어지게 된다.

이 경우 한가지 문제가 발생한다. 

# @curry 
def permutation (numbers, count = 1) :
    if len(numbers) <= count :
        return [[numbers[0]]]
    
    result = []
    for i, num in enumerate( numbers ) :
        Temp = numbers.copy() 
        del Temp[i]
        rest = permutation(Temp, count)
        result.extend( map( lambda x : [num, *x], rest ) ) 

    return result 


a = [1,2,3,4]
k = 2
count = ( len(a) - k + 1) 
result = (permutation(a, count))
print(result)
'''
[[1, 2], [2, 1], [3, 1], [4, 1]]
'''

바로 다음과 같이 한번만 순회하고 끝나는 문제가 발생하고 있다. 따라서 하나 깊게 있게 for문을 돌면서 nPr과 nPr-1이 같다는 점을 활용하여 위 처럼 코드를 작성한 것이다. 

 

이제 최종 코드는 아래와 같다. 

import sys

def permutation (numbers, count = 1) :
    if len(numbers) <= count :
        return [[numbers[0]]]
    
    result = []
    for i, num in enumerate( numbers ) :
        Temp = numbers.copy() 
        del Temp[i]
        rest = permutation(Temp, count)
        result.extend( map( lambda x : [num, *x], rest ) ) 

    return result 


n, k = map( int, sys.stdin.readline().split())
n = [ i for i in range(1,n+1)]

count = ( len(n) - k ) if ( len(n) - k  ) else 1
result = (permutation(n, count))

for _r in result :
    print(*_r[:k])