[BAEKJOON] 15654_N과 M(9)_Python

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

문제

 

* 프로젝트나 알고리즘 테스트나 한번 코드를 잘 짜놓으면 계속 쓸 수 있는 점을 다시 느꼈다.

 

문제 해설

(1) N, M, N개의 숫자 배열이 주어진다.
(2) 숫자 N개 중, M개를 뽑아 만든 수열을 사전순으로 출력하는 문제이다.
(3) 이번 문제는 (1, 2), (2, 1) 경우의 중복은 가능하나, 완전 동일한 중복은 허용하지 않는다.
이전 N, M 시리즈와 다른 것은 숫자배열에 똑같은 수가 들어있을 수 있다. 그래서 완전 동일한 수열이 나올 수가 있는 점을 주의해야 한다.

 

 

문제 풀이

https://chois95.tistory.com/59

[BAEKJOON] 15654_N과 M(6)_Python

에서 변형한 상태이다.

(1) 중복을 체크하되, N과M(6)에서처럼 sort한 것을 체크하는 것은 아니다. 완전 동일한 배열의 수열이 있는지만 체크해야 하기에, 원상태 그대로 answer set에 있는지만 검사하고 넣어준다.
(2) 수열조합을 만들때, 조합에 이미 있는 수여도 넣어줘야 한다. 현재 숫자리스트는 같은 수도 들어있기에 같은 수끼리 조합되는 경우도 허용해주어야 한다.

 

* 코드

from sys import stdin

N, M = list(map(int, stdin.readline().rstrip().split()))
num_list = list(map(int, stdin.readline().rstrip().split()))
num_list.sort()
answer = set([])


def get_sequence(arr, num_list):
    if len(arr) == M:
        new = ' '.join(map(str, arr))
        if not new in answer:
            answer.add(new)
            print(new)
        return

    for j in range(len(num_list)):
        arr.append(num_list[j])
        get_sequence(arr, num_list[:j] + num_list[j + 1:])
        arr.pop()


for i in range(len(num_list)):
    get_sequence([num_list[i]], num_list[:i] + num_list[i + 1:])