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

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

15663번: N과 M (9)

 

접근법이 쉽게 떠오르지 않아서 시간이 좀 걸렸다.

 

 

첫 번째 푼 방식은 시간 초과가 났었다.

함수 내부에서 또다른 함수를 호출해서 그런가..?

그냥 봤을 때 코드 자체도 복잡하긴 하다. ㅋㅋ

#시간 초과

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()