백준 15663번 N과 M (9) 파이썬

리뷰

리스트, 튜플, 세트, BFS를 짬뽕하여 풀었다. 이게 최적화 코드인지는 잘 모르겠다..

 

문제 풀이

1. n, m값과 숫자 리스트를 입력 받고 정답을 저장할 빈 set를 초기화 해준다.
2. BFS에 n과 m, 그리고 방문 처리와 임시 저장용 빈 리스트를 초기 기본값으로 세팅해준다.
3. 임시 리스트가 m의 길이와 같을 경우 해당 리스트를 튜플로 변환하여 set에 add를 해준다.
4. i번째 인덱스에 첫 방문일 경우 방문 처리 및 리스트에 값을 저장해 주고 재귀를 호출해 준다.
5. 이후 for문을 돌기 전에 방문처리와 추가했던 값을 다시 빼준다.
6. 모든 작업이 완료된 경우 set를 리스트로 변환 후 오름차순으로 정렬해 준다.
7. 정답 리스트를 순회하며 값이 저장된 리스트를 언패킹하여 출력해 준다.

 

참고 사항

set를 사용함으로서 자동으로 중복값이 제거가 된다.

임시 리스트가 m 길이에 도달 했을때 set에 리스트가 추가되지 않아 tuple로 변환해 주었다.

 

정답 코드

def bt(n, m, v=[], l=[]):
    if len(l) == m:
        ans.add(tuple(l))
        return
    for i in range(n):
        if i not in v:
            l.append(lst[i])
            v.append(i)
            bt(n, m, v, l)
            v.pop()
            l.pop()


n, m = map(int, input().split())
lst = list(map(int, input().split()))
ans = set()
bt(n, m)
ans = sorted(list(ans))
lst.sort()
for i in ans:
    print(*i)