[백준/Python] 15663번 : N과 M (9)

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

문제

N개의 자연수가 주어지고, M개를 고른 수열을 출력한다.

조건1. 중복되는 수열을 출력하면 안된다.
조건2. 사전 순으로 증가하는 순서로 출력한다.

풀이

사전 순으로 출력해야 했기 때문에 입력받은 N들을 sort() 로 정렬했다.

2가지를 고려해야 했다.

1. 똑같은 조합이 나오면 출력하면 안된다.

3 1
4 4 2

위의 입력의 경우, 결과가

2
4
4 # 중복이여서 안됨

 

위와 같이 똑같은 수열 4가 중복해서 출력되면 안된다.

2. 같은 수가 여러번 나올 수는 있다.
아래와 같은 입력의 경우

4 2
9 7 9 1

아래와 같이 숫자가 중복 될수는 있다. (9 9)

1 7
1 9
7 1
7 9
9 1
9 7
9 9 # 이건 가능

 

기본적으로 백트래킹을 이용해 풀었다.

1의 경우를 해결하기 위해, 같은 함수호출 수준에서  바로 앞에 어떤 것이 정답 배열(ans)에 있었는지 기억했다(prev).

2의 경우 때문에 set을 이용해 입력을 처리할 수 없었다.
또한 같은 숫자여도 다르게 취급해야 했기 때문에 defaultdict()를 활용했다. N들을 담은 리스트(li)에서의 인덱스를 key로 하여, ans에 들어간 경우 해당 value를 1로 바꿔주었다.

코드

from collections import defaultdict

n, m = map(int, input().split())

li = sorted(list(map(int, input().split())))

ans = []

def go(count, hist):
    if count >= m :
        print(' '.join(map(str,ans)))
        return
    else:
        prev = None
        for i, n in enumerate(li):
            if prev == n:
                continue
            else:
                if hist[i] == 1 : continue
                hist[i] = 1
                ans.append(n)
                go(count+1, hist.copy())

            prev = ans.pop(-1)
            hist[i] = 0

hist = defaultdict(int)
go(0, hist.copy())