[ BOJ / 파이썬 ] 15655 N과 M (6)

|  제출 1  |

# 백트래킹
import sys
input = sys.stdin.readline

#from itertools import permutations


N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))
keep = []
def recur(x):

  if len(keep) == M:
    print(" ".join(list(map(str, keep))))
    return

  
  for i in range(x, len(nums)):
    if nums[i] not in keep:
      keep.append(nums[i])
      recur(i+1)
      keep.pop()

recur(0)

 

: 으아 또 이틀 쉬고 보니까 한 번에 구조가 안 읽혔다. 차근차근 되짚어가니 풀 수 있었다.

 

: 해당 N과M의 키포인트는 정렬된 수 기준으로 한 번 스캔하고 각 스캔된 수의 다음 수부터 끝까지 재귀적으로 쭉 스캔하는 식이다.

: 처음 for문으로 기본 배열을 쭉 훑고 각각 들어갈 때 본인을 포함 안 하기 위해서, if nums[i] not in keep:구문을 넣어줬다. 그리고 해당 파트에서 현재 기준 값의 다음 값부터 끝까지 재귀적으로 돌고 프린트 찍힐 때마다 pop으로 꺼내 준다..

 

: 앞선 문제들과 거의 비슷하지만 큰 인덱스 범위를 잡아주는 데서 특징적인 문제였다.

 

 

|  제출 2  |

# combinations 사용 / 중복조합(순서O)

import sys
input = sys.stdin.readline

from itertools import combinations


N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))

for c in list(combinations(nums, M)):
  print(*c)

 

: 순서를 고려해서 중복 안 되게 뽑는 중복조합 사용 (combinations 메서드)

 

 

: combinations까지 써보니까 아무리 생각해도 이런 문제 앞의 N과M에서 했는데? 싶었는데 답, 로직은 같은데 그 때는 값이 있는 배열 인풋이 없었고 지금은 있는, 그런 차이였다. ( N과M(2) )