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

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

15663번: N과 M (9)

 

 

 

1차 시도

def backtracking():
    if len(res) == M:
        if res not in ans: # 수열 중복 방지
            ans.append(res.copy()) #res의 상태는 계속해서 변함. ans에는 res의 그 당시 값이 저장되어야 한다. 현재 참조 X
    else:
        for i in range(N):
            if not used[i]: # 값의 중복 방지
                used[i] = True
                res.append(lst[i])
                backtracking()
                used[i] = False
                res.pop()

N, M = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
res = []
ans = []
used = [False] * (N)
backtracking()
for idx in range(len(ans)):
    for num in ans[idx]:
        print(num, end=' ')
    print()

 

기존 N과 M 문제는 res를 바로 print 해주었다면, 이번 문제에서는 res.copy()를 append 해줘야 한다. 그 이유는 출력값으로 중복된 값을 가질 수 없기 때문에 중복 요소를 list를 사용해서 제거해주고자 했기 때문이다.

 

만일

if res not in ans: # 수열 중복 방지

라인을 주석 처리한다면, [[1, 7], [1, 9], [1, 9], [7, 1], [7, 9], [7, 9], [9, 1], [9, 7], [9, 9], [9, 1], [9, 7], [9, 9]]가 출력이 되고

 

추가적으로

ans.append(res)

로 코드 수정을 하면 [[], [], [], [], [], [], [], [], [], [], [], []] 가 출력이 된다. 

 

하여튼,,,

def backtracking():
    if len(res) == M:
        if res not in ans: # 수열 중복 방지
            ans.append(res.copy()) #res의 상태는 계속해서 변함. ans에는 res의 그 당시 값이 저장되어야 한다. 현재 참조 X
    else:
        for i in range(N):
            if not used[i]: # 값의 중복 방지
                used[i] = True
                res.append(lst[i])
                backtracking()
                used[i] = False
                res.pop()

N, M = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
res = []
ans = []
used = [False] * (N)
backtracking()
print(ans)
for idx in range(len(ans)):
    for num in ans[idx]:
        print(num, end=' ')
    print()

이 코드를 실행하면 시간 초과가 뜬다.

Python Answer

def backtracking():
    if len(res) == M:
        ans.add(tuple(res))
    else:
        for i in range(N):
            if not used[i]:
                used[i] = True
                res.append(lst[i])
                backtracking()
                used[i] = False
                res.pop()

N, M = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
res = []
ans = set()
used = [False] * N
backtracking()
answer = list(ans)
answer.sort()
for idx in range(len(answer)):
    for num in answer[idx]:
        print(num, end=' ')
    print()

 

시간을 줄이기 위해 res not in ans 대신 set 데이터 구조를 이용했다. res not in ans는 res마다 전부 리스트 전체를 봐야 하므로 부하가 온다. 리스트 대신 튜플을 사용하여 원소의 순서가 변화하지 않도록 하며, set로 중복을 걸러주었다.

 

+ 그리고... ans.append(res.copy())를 했는데 튜플은 그냥 add하면 되는 이유는 정말 간단함! immutable 자료형이니까! 참고로 set에 list를 add할 수는 없다. set의 요소로는 가변 자료가 오면 안 된다!