💡문제 분석 요약
- N개의 숫자 중에서 M개를 뽑아 순열로 출력한다.
- 이때 중복된 숫자는 출력하지 않는다. ex) 4 4 2중에서 1개 출력하면, 2 4만 출력됨.
💡알고리즘 설계
- DFS 사용 : 백트래킹은 DFS, BFS 둘 다 가능하지만 재귀를 사용한다는 점과 되돌아온다는 맥락에서 DFS가 더 편하고 적합했다.
💡코드
n, m = map(int, input().split())
lst = sorted(list(map(int, input().split())))
visited = [0] * n
temp = []
def backTracking(): # DFS를 이용함
if len(temp) == m: # 출력조건. m개의 숫자가 쌓일 때까지 백트래킹을 진행함. 다 모이면 출력
print(*temp)
return
prev = 0 # 이전의 값
for i in range(n): # m개의 숫자가 모이는 과정인데, prev를 통해 중복 출력을 방지함.
if prev != lst[i] and not visited[i]: # 이전값과 현재값이 다르고, 방문안한 경우
visited[i] = True # 방문처리
temp.append(lst[i]) # 현재값 temp에 넣음 (m개까지 모을거임)
prev = lst[i] # 현재값은 이제 prev값으로 바뀜
backTracking()
# 재귀 호출이 끝나면 방문 여부를 해제 & 마지막으로 추가한 요소를 제거
visited[i] = False
temp.pop()
backTracking()
💡시간복잡도
- 최악의 경우, O(n^m)이 된다. 물론 실제로는 m개의 원소가 쌓이면 빠져나오므로 이보다는 적은 시간이 걸릴 것으로 보인다.
💡 틀린 이유
- 백트래킹 개념에 익숙하지 않아 어려웠다.
- prev를 설정하는 것을 떠올리지 못했는데, 그 이유는 처음부터 정렬해서 입력받을 생각을 못했기 때문이다.
💡 틀린 부분 수정 or 다른 풀이
- 정렬 후, prev를 통해 같은 값은 다시 탐색하지 않도록 설정한다.
💡 느낀점 or 기억할정보
- print(*list) : 리스트의 원소를 한 칸 씩 띄어서 출력한다. ex) list = [1,2,3]이고 print(*list)라고 하면 1 2 3 이렇게 출력한다.
반응형
'알고리즘 > 코테 스터디 (2024)' 카테고리의 다른 글
6987 월드컵 (5) | 2024.07.24 |
---|---|
15651 N과 M (3) (0) | 2024.07.23 |
1743 음식물 피하기 (5) | 2024.07.21 |
2178 미로 탐색 (3) | 2024.07.20 |
1697 숨바꼭질 (0) | 2024.07.19 |