백준 15650번 - N과 M(2) - 순열 (with Python3)

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

 

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

예제

# 입력
4 2

# 출력
1 2
1 3
1 4
2 3
2 4
3 4

# 입력
4 4

# 출력
1 2 3 4

Coding - Python3

기본 순열 문제에서 코드 몇개만 수정하면 된다.

 

참고. 기본 순열 문제

2020/04/03 - [Algorithm/Beakjoon] - 백준 Ex.15649번 - N과 M(1) 순열 문제 (with Python3)

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

 

오름차순으로 정렬해야하기 때문에 stack에 값을 넣을때, 이전 원소보다 큰 원소만 넣을 수 있도록 조건문을 추가한다.

# -*- 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 or (stack and stack[-1] > i):
                    # 이미 뽑은 숫자이거나
                    # 스택이 비어있지 않고, 이전 원소보다 작은 경우 뽑지 않는다.
                    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)

 

채점 결과

Reference

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