백준 15649번 - N과 M(1) 순열 문제 (with Python3)

본 문제는 백준 알고리즘(https://www.acmicpc.net/)에게 있습니다.

 

1. 문제

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

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

1.1. 예제

      

      

      

    
    

      <python />
    
# 입력
3 1

# 출력
1
2
3

      

      

      

    
    

      <python />
    
# 입력
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

 

2. Coding - Python3

대표적인 순열 문제로 푸는 방식만 익히면 쉽게 문제를 풀 수 있다.

 

for 문을 이용하는 방식과 재귀함수를 이용하는 방식이 있는데, 재귀 함수로 푸는것이 이해하기 쉽다.

아래 코드는 stack 과 재귀 함수를 이용하여 문제를 풀었다.

      

      

      

    
    

      <python />
    
# -*- coding: utf-8 -*-

import sys


def solution(n, m):

    def search(stack, visit, n, m):
        if len(stack) >= m:
            print(" ".join(map(str, stack)))
        else:
            for i in range(1, n + 1):
                if i in visit:
                    continue  # 이미 사용했던 숫자는 다시 뽑지 않는다.

                visit.add(i)
                stack.append(i)  # 선택한다.

                search(stack, visit, n, m)

                visit.remove(i)
                stack.pop()  # 선택하지 않는다.

    search(list(), set(), n, m)


if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().strip().split())
    solution(n, m)

 

채점 결과

참고로 파이썬에는 순열을 만들어주는 메소드가 존재한다. 하지만, 알고리즘 공부를 위해 본 글에서는 사용하지 않았다.

      

      

      

    
    

      <python />
    
import itertools

itertools.permutations(LIST, N)

3. Reference

• https://www.acmicpc.net/problem/15649