[백준/python] 15655번: N과 M (6)

문제

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

15655번: N과 M (6)

---

문제 요약

N개의 수를 입력 받고, 그 중 M개를 고른 수열을 오름차순으로 출력한다.

 

+ 위 링크의 예제 입출력 참고

 

---

코드

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

def go(check, start):
    # check의 i번째 요소가 1이라면 arr[i]를 사용한 것(출력할 것)이다.
    #print(check)
    if sum(check) == m: # 출력할 수가 m개이어야 출력
        ans = [arr[i] for i in range(n) if check[i]]
        print(' '.join(map(str, ans)))
        return # 함수 종료 -> 이전 함수로 돌아간다.
    for i in range(start, n): # start인덱스부터 끝까지 체크되지 않은 수를 찾는다.
        if check[i] == 0: # arr[i]가 아직 사용한 수가 아니라면
            check[i] = 1 # 사용했다고 체크하고
            go(check, i+1) # 체크한 리스트를 다시 함수에 넣는다. 
            # start인자에 i+1을 넣어 이전 함수에서 체크된 인덱스보다 큰 수에서만 체크되지 않은 수를 찾는다.
            check[i] = 0 # 위에서 호출한 재귀함수가 종료되면, 다시 check를 0으로 되돌린다. (3번 중첩된 함수 모두)

n, m = map(int, input().split())
arr = sorted(list(map(int, input().rstrip().split())))

go([0] * n, 0)

---

코드 설명

1. 입력 받을 자연수 개수 n, 자연수들 중 골라서 출력할 개수 m, n개의 자연수를 갖는 리스트 arr을 입력받는다. (오름차순으로 출력해야 하므로 sorted함수를 이용하여 정렬한다.)

---

2. go함수를 정의한다. (재귀 함수)

 

3. go 함수는 인자로 배열 check와 int형 변수 start를 받는다.

 

3-1. 배열 check의 i번째 요소가 1이라면 arr의 i번째 요소는 이번 출력에 사용할 예정인 요소이다.

+ 출력 예정이 아닌 요소는 0.

 

3-2. start는 go를 호출한 이전 go함수에서 출력할 요소로 선택된 인덱스의 다음 인덱스이다.

+ 반복문에서 start 인덱스부터 check의 끝까지 탐색하며 0인 인덱스를 찾는다.

(처음엔 인덱스 0부터 탐색해야하므로 초기 값은 0.)

 

4. 출력 예정인 요소가 m개라면 (check 요소들 중 1 개수가 m개라면) check의 요소가 1인 인덱스의 arr요소들을 출력하고 현재 go 함수를 종료한다.

+ 현재 go 함수를 종료하고 현재 함수를 호출한 이전 go 함수로 돌아간다.)

 

5. 출력 예정인 요소가 m개가 아니어서 함수가 종료되지 않았다면 start인덱스부터 check 끝까지 반복문을 이용하여 출력할 요소(check가 0인 요소)를 찾는다.

 

5-1. 출력할 요소를 찾았다면, check를 1로 변경한다.

 

5-2. 변경한 check 리스트와 출력할 요소의 다음 인덱스를 check와 start값 인자로 넣고 go 함수를 다시 호출한다.

+ start 인자에 i+1값을 넣어 이전 함수에서 체크된 인덱스보다 큰 인덱스들에서만 함께 출력할 요소를 찾는다.

 

5-3. 현재 함수에서 호출한 함수가 종료되면 (출력할 요소 m개를 찾아 종료된 것), 출력한 check값을 다시 0으로 되돌린다.

---

6. 초기 함수 인자 check에 n개의 0값을 갖고 있는 리스트, start에 0을 넣고 go 함수를 호출한다.

---

재귀 함수를 공부하기 좋은 문제이므로 천천히 각 줄 코드의 의미를 해석하며 공부해보자.

 

복습은 필수!