[ BOJ / 파이썬 ] 15657 N과M(9) (*다시 체크 요망, 덜 이해한듯*)

|  제출 2  |

# 백트래킹 사용한 풀이
import sys
input = sys.stdin.readline

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

keep = []
visit = [0]*N

def recur(x):

  if x == M:
    print(*keep)
    return

  overlap = 0  # 이 부분 직접 해결한 것 아님. 다시 확인해보기
  for i in range(N):
    if not visit[i] and overlap != nums[i]:
      visit[i] = 1
      keep.append(nums[i])
      overlap = nums[i]
      recur(x + 1)
      visit[i] = 0
      keep.pop()
      
      
recur(0)

 

하 .. 맞긴 맞았는데, 

overlap부분 아이디어를 내가 떠올린게 아니다..

다른 분 블로그 글 보고 차용했다.

 

 

|  제출 1  |

 

# 망한거 기록용

import sys
input = sys.stdin.readline

from itertools import combinations_with_replacement


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

keep = []
visit = [0]*N
index = 0

def recur(index, x):

  if x == M:
    print(keep)
    return
    
  for i in range(N):
    if len(keep) == 0:
      index += 1
    # 💥 이 부분 해결 위해 index란 값 설정해서 여기저기 배치해준 것.
    if not visit[i] or (nums[i] in keep and nums[index] == nums[i]): 
      visit[i] = 1
      keep.append(nums[i])
      recur(index, x + 1)
      keep.pop()
      
      
recur(-1, 0)

# 중복도 해결 못하고 값도 제대로 안 나옴

: 중복 문제를 해결하기 위해 이리 꼬고 저리 꼬다가 의도와는 전혀 멀어졌다.. 생각 다시 정리해보겠다.

 

 

 

|  제출 3  |

 

import sys
input = sys.stdin.readline

from itertools import combinations_with_replacement


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

keep = []
visit = [0]*N
result = set()

def recur(x):

  if x == M:
    result.add(tuple(keep))
    return

  
  for i in range(N):
    if not visit[i] :
      
      visit[i] = 1
      keep.append(nums[i])
      recur(x + 1)
      visit[i] = 0
      keep.pop()
      
      
recur(0)
for res in sorted(list(result)):
  print(*res)

 

제출 1 같은 경우는 overlap변수가 도통 안 와닿아서 그냥 중복을 자체적으로 제거하는 set을 쓰는게 이해가 편해서 다시 풀엇다. 

그러면 원래 내가 풀이한대로 하고, set을 list로 잘 변환만 해주면 된다.