[백준/python] 15663번: N과 M (9)

문제

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

15663번: N과 M (9)

---

문제 요약

N개의 자연수들이 주어졌을 때, 조건을 만족하는길이가 M인 수열을 모두 출력한다. (사전 순)

+ 예제 입출력을 확인 후 조건을 파악한다. 

 

이 코드에서 주의해야할 점은 중복된 수를 입력 받았을 때, 중복된 개수만큼 여러번 그 수가 사용될 수 있다는 점이다. 

---

코드

import sys
input = __import__('sys').stdin.readline

def go(arr):
    if len(arr) == m:
        print(' '.join(map(str,arr)))
        return
    for i in range(len(List)):
    # n이 아니라 중복된 수를 제거한 리스트안의 요소 개수만큼 반복
        if arr.count(List[i]) < dic[List[i]]:
        # List[i]를 입력 받은 개수보다 출력할 배열 arr안에 있는 개수가 적을 때
            arr.append(List[i])
            go(arr)
            arr.pop()
            
n, m = map(int,input().split())
# 입력 받을 자연수 개수 n, 출력할 수열의 길이 m
List = list(map(int, input().split()))
# N개의 자연수들을 리스트로 저장
List.sort()
# 사전 순으로 출력해야하므로 정렬

dic = {}
# 요소들이 몇 번 등장하는지 저장하는 딕셔너리
for i in range(n):
    if List[i] in dic.keys():
        dic[List[i]] += 1
    else:
        dic[List[i]] = 1

List = sorted(list(set(List)))
# 요소들의 등장 횟수를 딕셔너리에 저장했으므로 중복된 수 제거

go([])

---

코드 설명

1. N개의 자연수들을 입력 받고, 배열 List에 저장한 후 사전 순으로 출력해야 하므로 정렬한다.

 

2. List의 요소들 중 같은 요소가 몇 번 등장하는지 저장하는 딕셔너리를 생성한다.

 

2-1. 요소들의 등장 횟수를 딕셔너리에 저장했으므로 중복된 집합 set 함수를 이용하여 중복된 요소들을 제거한다.

 

3. go 함수를 호출한다.

 

3-1. List의 첫 번째 요소부터 탐색하며 입력 받은 횟수보다 arr안에 있는 개수가 적다면 arr에 추가하고 다음 arr에 넣을 요소를 찾기 위해 go 함수를 다시 호출한다. (재귀)

+ arr는 출력할 요소들을 저장하는 배열이다.

 

3-2. go 함수의 인자 arr의 요소의 개수가 출력할 개수만큼 가득찼다면, arr의 요소들을 출력하고 함수를 종료시킨다. 

=> 함수가 종료되면 arr에 넣은 수는 다시 빼준다. (백 트래킹)

---

완전 탐색 (백트래킹)을 이해하는데에 N과 M 시리즈는 매우 도움이 되므로 모두 풀어보는 것을 추천한다.