백준 - 15650

문제 설명

백준의 기본 백트래킹 시리즈의 2번째 문제다.

1부터 N까지의 자연수 중 중복없이 M개를 고른 수열을 출력해야 하며, 고른 수열이 오름차순이여야 한다.

즉, 1 2 3 4 는 출력이 가능하지만, 1 2 4 3 은 불가하다.

---

접근 방식

• N과 M 1번 문제와 비슷한 백트래킹을 수행하면 되는데, 출력이 오름차순으로 수행되는 부분만 신경쓰면 된다.
  
  
• 주어진 범위내에서 백트래킹을 수행하며, 출력 단에서 오름차순인 경우에만 출력하도록 sorted()를 이용해 생성된 배열과 비교 후 같을 때만 출력하도록 할 수도 있다.
  -> 버전 1.
  
  
• 주어진 범위내에서 재귀를 수행할 때, 함수의 파라미터로 (현재 탐색 위치+1)을 집어넣는 연산을 수행하여, 각 자리가 채워졌을 때 다음 자리는 나보다 큰 수만 올 수 있게 할 수 있다.
  -> 버전 2의 back(i+1)
  
  
• itertools의 combinations를 이용해 주어진 범위내에서 가능한 경우를 조합하게끔 코드를 작성할 수 있다.
  -> 버전 3.

---

작성한 코드

• 버전 1. sorted() 이용

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
result = []

def back():				# 백트래킹을 위한 재귀 함수
    sorted_list = sorted(result)
    
    if len(result) == m:	# 길이가 m이면 출력
        if result == sorted_list:
            print(' '.join(map(str, result))) 
            return
    
    for i in range(1, n+1):		# 사용 가능한 자연수 범위 내에서
        if i in result:			# 배열에 문자가 있으면 넘어감
            continue
       
        result.append(i)		# 결과에 넣고 
        back()	    			# 재귀가 끝나면
        result.pop()			# 다시 빼줌

back()

• 버전 2. for문 이용

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
result = []

def back(num):				# 백트래킹을 위한 재귀 함수
    sorted_list = sorted(result)
    
    if len(result) == m:	# 길이가 m이면 출력
        print(' '.join(map(str, result))) 
        return
    
    for i in range(num, n+1):	# 사용 가능한 자연수 범위 내에서
        if i in result:			# 배열에 문자가 있으면 넘어감
            continue
       
        result.append(i)		# 결과에 넣고 
        back(i+1)				# 재귀가 끝나면
        result.pop()			# 다시 빼줌

back(1)

• 버전 3. combinations 이용

import sys
from itertools import combinations          # 조합 생성

input = sys.stdin.readline

n, m = map(int, input().split())

result = combinations(range(1, n+1), m)     # 1 ~ n 까지의 범위에서 
                                            # m개의 가능한 모든 수열 추출
for i in result:
    print(" ".join(map(str, i)))            

---

수행시간

56ms -> 버전 2
40ms -> 버전 3
164ms -> 버전 1

확실히 정렬에 쓰는 시간이 불필요하게 많은 것 같다.

또한, combinations를 썻을 때가 가장 빠른 처리를 함에 놀랐다.