[ BOJ / 파이썬 ] 15650 N과 M (2)

|  제출 1  |

 

import sys
input = sys.stdin.readline

from itertools import combinations

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

result = list(combinations(range(1,n+1), m))

for r in sorted(result):
  print(' '.join(list(map(str,r))))

 

: 파이썬의 combinations 라이브러리를 사용한 풀이입니다.

: combinations는 중복 없는 순열을 찾는 라이브러리입니다.

: 출력 시에 각 순열의 아이템을 str 형태로 바뀐 뒤 문자열로 붙여 출력하게 했습니다. 

 

combinations

중복조합: 중복을 허용하지 않고 뽑음. 조합이므로 순서는 상관 없음.

combinations( 반복가능 객체, 뽑는 수 )

 

 

 

|  제출 2  |

 

import sys
input = sys.stdin.readline

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

group = []
result = []
def find():

  if len(group) == m:
    if not sorted(group) in result:
      result.append(sorted(group))
    return

  for i in range(1, n+1):
    if i not in group:
      group.append(i)
      find()
      group.pop()

find()
for r in result:
  print(' '.join(list(map(str, r))))

 

: 백트래킹을 사용한 풀이

 

1.  중점적으로 볼 부분은 아무래도 재귀 부분! 

 

: 순차정렬이라고 했으니까 만들 때부터 1부터 n까지 밀어넣어본다.

 

: 순간 헷갈렸던 게 저 if i not in group 인데, 중복 없게 하려는 의도이다.

 

: i가 들어갔을 때의 경우를 find()안에서 쭉 찾게 된다. 그 전의 내용들은 물론 i보다 작은 수의 경우 찾기에서 해소되었고, 지금 보는 부분은 i가 그룹에서 제일 작을 때!

 

: i에 대한 계산이 끝나면 group.pop()으로 i 빼주고 그 다음 i+1로 그룹에서 제일 작은 녀석을 설정해주는게 for문의 역할이다. ( 요게 이 문제 핵심 )

 

 

2. N과 M(1) 과 해당 문제가 달랐던 부분은 아무래도 순열들간에 중복도 없어야 한다는 점이었다. 

그래서 위와 같이 result 배열을 만들고 기존 값과 겹치는지 체크해서 겹치지 않을 때만 넣어주게 했다.

이 때, 오름차순이라는 조건 덕분에 비교가 더 쉬웠다. 

 

그리고 마지막에는 for in문으로 돌아가며 한 줄씩 출력한다.

리스트 형태로 넣어줬기 때문에 한 번에 join하면 [ ] 기호가 섞여나오기 때문이다.