백준 N과 M (9) ~ (12) / 파이썬 백트래킹

문제번호	문제이름
15649	N과 M (1)
15650	N과 M (2)
15651	N과 M (3)
15652	N과 M (4)
15654	N과 M (5)
15655	N과 M (6)
15656	N과 M (7)
15657	N과 M (8)
15663	N과 M (9)
15664	N과 M (10)
15665	N과 M (11)
15666	N과 M (12)

지난 포스팅에서는 약간 응용을 하면 8번까지 풀이 가능한 1번 문제에 대한 코드를 살펴보았다.

 

이번에는 9번문제를 다뤄보도록 하겠다.

백준에서 N과M 9번 문제만 유일하게 정답률이 50%미만이다. 오늘날짜로 약 49% 이다.

 

N과 M (9)

www.acmicpc.net/problem/15663

15663번: N과 M (9)

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

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

이전 1번 문제와 달라진 부분 첫번째는 임의의 숫자 배열이 주어진다는 것이다.

즉, 이전 8번문제까지는 숫자 배열 자체에서 중복이 발생하지 않았지만, 이번 문제부터는 중복된 숫자가 발생한다.

따라서 이전에 사용했던 arr배열의 숫자가 ary 배열내에 존재하는지 체크하기위해서 다른 방식을 사용해야한다.

 

두번째는, 달라진 부분이라기보다 이 문제에서 처리해야하는 또 한가지의 문제이다.

기본적으로 N과 M 문제들은 중복되는 수열은 출력하면 안된다. 하지만 이 문제를 풀때에는 중복된 숫자들이 있으므로 같은 조합을 여러번 만들어 낼 수 있다. 따라서 이 부분또한 처리해야 한다.

 

풀이

앞서 말했던 두번째 문제부터 처리하자. 파이썬 collections 라이브러리에서 제공하는 defaultdict 모듈을 사용하면 쉽게 처리가능하다.

from collections import defaultdict
dic = defaultdict(int)
...

함수내에서
if  dic[tuple(ary)] == 0:
	dic[tuple(ary)] = 1
	for j in ary:
    	print(j, end = ' ')
    print()
    return

우선 defaultdict 의 쓰임은, 파이썬 딕셔너리에서의 key error를 방지하기 위함이다.

파이썬 딕셔너리를 사용할때는 key : value 쌍으로 저장해야하는데, 이 쌍이 없는 key를 참조할 경우, 즉 이전에 값을 저장해두지 않은 key를 참조할때는 key error가 발생한다.

그래서 이 key가 있는지 없는지 조사를 하기위해서는 몇줄의 코드를 작성해야한다.

하지만 defaultdict(int)라고 선언할 경우 모든 key 입력에대해(저장되어있지 않은 key) 기본적으로 0을 반환한다.

그러므로 key error를 없앨 수 있다.

 

tuple(ary)를 사용한 이유는 key 에는 list 대신 tuple을 써야하기 때문

 

이제 첫번째 문제를 해결하러 가자.

 

이 문제에서는, 이전과 달리 중복가능한 숫자 배열을 입력으로 받는다.

그렇기에 가능한 조합을 구성해낼때 단순히 어떤 숫자가 내가 만들 순열배열에 있는지 없는지 조사하게 되면 같은 숫자가 여러개 있을 수 있으므로 적절한 조합을 생성해내지 못한다.

 

따라서 내가 생각한 방법은, 내가 선택해온 숫자들의 인덱스를 저장하는 인덱스 배열을 사용하는 방법이다.

그러면 0번째에있던 1과 3번째에있던 1을 인덱스 번호로 구별해낼 수 있게 된다.

 

import sys
from collections import defaultdict
input = sys.stdin.readline

n,m = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
dic = defaultdict(int)

def ccc(ary,idx):
    if len(ary) == m :
        if  dic[tuple(ary)] == 0:
            dic[tuple(ary)] = 1
            for j in ary:
                print(j, end = ' ')
            print()
            return
        else:
            return
    
    for i in range(len(arr)):
        if i not in idx:
            idx.append(i)
            ary.append(arr[i])
            ccc(ary,idx)
            idx.pop()
            ary.pop()
 
ccc([],[])

 

idx 라는 인덱스 배열을 만들고, 내가 지나온 길을 표시해준다.

그리고 반복문 내에서는 내가 지나온 인덱스에 있는지 없는지만 검사해주면 된다.