Coding/백준
[Python] 백준 15663번 - N과 M (9)
leta
2022. 2. 26. 18:49
문제 https://www.acmicpc.net/problem/15663
15663번: N과 M (9)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
접근법이 쉽게 떠오르지 않아서 시간이 좀 걸렸다.
첫 번째 푼 방식은 시간 초과가 났었다.
함수 내부에서 또다른 함수를 호출해서 그런가..?
그냥 봤을 때 코드 자체도 복잡하긴 하다. ㅋㅋ
#시간 초과
import sys
input = sys.stdin.readline
def inter_dfs(i):
global ans, num
ans.append(num[i])
dfs()
ans.pop()
def dfs():
if len(ans) == m and ans not in anss:
anss.append(ans[:])
print(*ans)
return
elif ans in anss:
return
for i in range(n):
if num.count(num[i]) > 1:
inter_dfs(i)
else:
if num[i] not in ans:
inter_dfs(i)
n, m = map(int, input().split())
num = list(map(int, input().split()))
num.sort()
ans = []
anss = []
dfs()
visited 배열과 same 변수를 사용해서 시간 초과를 해결하였다.
visited 배열을 통해 방문한 숫자들을 구분해준다.
same 변수는 중복된 수를 빼기 위함이다.
입력받은 수들을 정렬한 후에 dfs 함수를 실행하면,
중복된 수들을 수열에 한 번만 넣을 수 있다. (if not visited[i] and same != num[i]:)
... 머리로는 이게 맞는데.. 글로 풀어쓰기가 어렵다.
#통과 코드
import sys
input = sys.stdin.readline
def dfs():
if len(ans) == m:
print(*ans)
return
same = 0
for i in range(n):
if not visited[i] and same != num[i]:
visited[i] = 1
ans.append(num[i])
same = num[i]
dfs()
ans.pop()
visited[i] = 0
n, m = map(int, input().split())
num = list(map(int, input().split()))
num.sort()
ans = []
visited = [0] * n
dfs()