프로그래밍/Python
[Python] 백준 15663 N과 M (9)
모영이
2021. 3. 8. 18:38
15663번: N과 M (9)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
백트래킹 : 중복되는 수열을 제외해야한다. 2 4 4가 있고 길이가 2이면 2 - 4(첫번째 4) 2 - 4(두번째 4)가 중복된다. 주어진 수를 제거하면 안되는게 2 4 4에서 중복되는 4를 제거하면 2 4가 되어 4 - 4 수열을 체크 못한다. 그래서 중복되는 값을 없애야하고 자연스럽게 in을 사용했지만, in은 시간복잡도가 list와 tuple일때 O(N)이지만 set, dict일때 O(1)이다. 그래서 set을 사용했다.
전체코드
import sys
import copy
input = sys.stdin.readline
def bt(t, result_each, visited_each):
if t == 0:
if tuple(result_each) not in result_total:
result_total.add(tuple(result_each))
print(*result_each)
return
for i in range(N):
if i not in visited_each:
bt(t - 1, result_each + [nums[i]], visited_each + [i])
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
result_total = set()
bt(M, [], [])