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

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

15663번: N과 M (9)

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 백트래킹

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

 

---

 

기존의 앞선 N과 M 시리즈에서 몇가지 기능이 추가되었다.

 

우선 수를 정렬하여 뽑으면서

 

같은 자리의 숫자를 중복하지 않고

 

앞서서 나온 숫자들 중에 중복되지 않아야 한다.

 

4 2
9 7 9 1

위의 예시를 들면

 

정렬하면

1 7 9 9

이를 2개씩 순서대로 뽑으면 같은 자리의 중복 없이 뽑는다면

 

1 7
1 9
1 9 (중복)
7 1
7 9
7 9 (중복)
9 1
9 7
9 9
9 1 (중복)
9 7 (중복)
9 9 (중복)

위와 같으므로 정답은

 

1 7
1 9
7 1
7 9
9 1
9 7
9 9

위와 같이 나오게 되는것이다.

 

질문게시판의 한 예를 가져오면

 

4 3
1 9 9 9

정답
1 9 9
9 1 9
9 9 1
9 9 9

위의 순서대로 나오게 된다.

 

내가 푼 방식은

 

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

arr = list(map(int, input().split()))
arr.sort()
stack = []
visited = []
visited2 = [ False for _ in range(n)]
def dfs(now, index): #현재 위치, 스택의 길이
    global visited
    if index == m:
        if ' '.join(stack) not in visited: #정답으로 출력되지 않은 경우
            print(' '.join(stack))
            visited.append(' '.join(stack)) #정답 리스트에 추가
            return
        else:
            return
    for i in range(n):
        if len(stack) != 0 and now == i: #같은 자리의 중복 방지
            continue
        if not visited2[i]:
            stack.append(str(arr[i]))
            visited2[i] = True #자리 체크
            dfs(i, index+1)
            stack.pop()
            visited2[i] = False
                
dfs(0, 0)

visited 배열은 중복된 정답을 체크하는 용도

visited2 배열은 stack에 넣는 과정에서의 자리를 체크한다.

 

이를 Python3로 제출하면 시간초과가 발생한다.

 

총 8가지의 숫자 배열이 올 수 있는데

 

이 경우의 수는 8! = 40,320의 경우의 수이므로

 

모든 리스트를 하나하나 확인하는 경우 시간초과가 발생한다. 그래서 PyPy3로 제출하여 정답을 맞출 수 있었다.

 

이에 내가 푼 코드가 맘에 안 들어서 다른 사람의 코드를 보았는데

 

정말 심플하고 간결했다.

 

---

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = input().split()
arr.sort(key=int) #key=int 없으면 값이 달라짐
stack = []
visited = [0] * n

def dfs(index):
    if index == m:
        print(' '.join(stack))
        return
    now = -1 #자연수이므로 -1로 초기화
    for i in range(n):
        if visited[i] or now == arr[i]: #방문했거나, 값이 같다면 넘기기
            continue
        visited[i] = 1
        stack.append(arr[i])
        dfs(index+1)
        visited[i] = 0
        now = stack.pop() #가장 마지막 값을 빼면서 결과값의 중복 체크

dfs(0)

위의 코드를 예로

 

4 3
1 9 9 9

를 풀어보면

 

처음에 stack = ['1', '9'] 까지는 쉽다.

그다음 다시 재귀를 타면서 now = -1이고 3번째 9인 visited[2] = 0이기 때문에 stack = ['1', '9', '9']가 된다.

 

이후 index = 3이 되면서 return 되고 visited[2] = 0, now = 9 가 된다. ( stack.pop()을 하면서 9를 리턴)

 

이후 다음 반복문인 i = 3일 때 visited[3] = 0이지만 now = 9이면서 arr[3] = 9와 일치하므로 중복이다.

 

이후 for반복문을 모두 돌았기 때문에 원래 재귀로 돌아가며 stack = ['1', '9'] -> ['1'] -> [ ] 상태로 돌아가며 for문의 i = 1로 올라가게 된다.

 

i=1에 해당하는 arr[1] 은 9 이므로 stack = ['9'] 이후 위와 같은 반복이다.

 

조금만 더 생각했더라면? 하고 아쉬우지 않을 정도로

 

내 풀이방식과는 완전 달랐다.

 

처음에 풀 때는 자연수인 점을 활용해 0부터 시작하는 것도 생각해 보고

 

stack.pop()으로 리턴된 수를 이용해보려 하였으나 생각이 저렇게까지 닿지 못했다.

 

여러모로 아쉬웠다.