백준 15663 n과m 9번 -python
문제풀이
- n과 m 이전 문제들과 다를게 없다라고 생각했는데…. 시간이 상당히 오래걸렸다.
- 중복제거를 위해 배열 하나를 더 만들어서 해당 배열에 같은 값이 없을 때만 넣어주는 방식으로 해결했다.
- python3는 시간초과…pypy3로 통과해서 다시 풀어봐야겠다…
- 같은 깊이일때 중복을 해결하는 방식으로 풀어봐야겠다.
- 두번째 코드
code
처음 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# python3로 통과하지 못하고 pypy3로 통과한 코드
## not in 을 사용했기 때문에 메모리와 시간이 매우 큼
def f(index, n, m):
if(index == m):
a = ""
for i in res:
a += str(i)+" "
if(a not in box):
box.append(a)
return
else:
for i in range(n):
if(visited[i] == 0):
visited[i] = 1
res[index] = arr[i]
f(index+1, n, m)
visited[i] = 0
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
visited = [0 for i in range(n)]
res = [0] * m
box = []
f(0, n, m)
for i in box:
print(i.rstrip())
두번째 코드
- 위에서 생각했던 방식으로 재귀를 타면서 체크를 하는게 아닌 다 뽑아낸 후
dict형을 이용해서 중복제거 - check에서 array로도 해보고 dict로도 중복을 제거해 봤지만 dict는 속도가 매우 빠른 반면 array는 시간초과가 발생…
- 이 부분에 대해서는 좀 더 공부를 해 봐야겠다…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def f(index, n, m):
if(index == m):
a = ""
for i in res:
a += str(i)+" "
box.append(a)
return
else:
for i in range(n):
if(visited[i] == 0):
visited[i] = 1
res[index] = arr[i]
f(index+1, n, m)
visited[i] = 0
## dict로 중복을 제거했을 때
def check(box):
check = {}
idx = 0
for item in box:
if item not in check:
check[item] = True
box[idx] = item
idx += 1
del box[idx:]
## array로 중복을 제거 했을 때
def check(box):
checks = [0] * len(box)
idx = 0
for item in box:
if item not in checks:
checks[idx] = item
box[idx] = item
idx += 1
del box[idx:]
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
visited = [0 for i in range(n)]
res = [0] * m
box = []
f(0, n, m)
check(box)
for i in box:
print(i)
