15663 N과 M (9)

💡문제 분석 요약

• 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 이렇게 출력한다.