[백준/Python] 15666번: N과 M (12)

15666번: N과 M (12) (acmicpc.net)

15666번: N과 M (12)

---

문제 해석

N개의 자연수 중 M개를 고른 수열을 모두 구하는 문제이다.

조건으로는 같은 수를 여러 번 골라도 되고 비내림차순이어야 한다. 그리고 순열은 사전 순으로 출력해야 한다.

---

코드

---

문제 풀이

main부분을 보면 s에 N개의 수를 저장해 주었고 s를 오름차순으로 정렬해주었다. 이는 사전 순으로 출력해주기 위함이다.

그리고 arr와 result를 각각 list와 dictionary로 선언해주었는데 arr에는 순열이 저장되고 result에는 조건에 맞는 순열들을 모아서 저장해 주었다. 여기서 result는 dictionary로 선언한 이유는 hash table을 이용하기 때문에 list보다 탐색 시간이 훨씬 빠르기 때문이다.

go function를 보면 처음 if문에서는 재귀의 종료조건을 정의해주었는데 처음 if문으로 arr가 M 길이에 도달했을 때를 정의해주었다. 2번째 if문에서는 중복되는 순열을 골라내기 위한 것으로 먼저 arr는 list이기 때문에 탐색할때 불편하므로 a에 string문으로 변환하여 저장해주었고 result에 같은 값이 없을 경우, 이 값을 출력하였다.

go function의 for문에서는 백트래킹을 수행하는데 맨 처음 수행할때는 아무 조건없이 곧바로 수행하게 하였고 2번째부터는 비내림차순으로 순열을 만들어야 하므로 if문에 조건을 달아놨다.

 

여담으로 arr를 a로 변환하는 과정에서 굳이 "".join()이 아닌 " ".join()인 공백을 추가한 이유는
4 3
1 11 111 1111
이라는 반례가 있기 때문이다.