[백준] 15650-N과M(2)

문제 바로가기

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, sys.stdin.readline().split())
answer = []
ans = []
def back():
    if len(answer) == M and sorted(list(answer)) not in ans:
        ans.append(list(answer))
        return
    for i in range(1, N+1):
        if i not in answer:
            answer.append(i)
            back()
            answer.pop()
back()
ans = sorted(ans)

for j in ans:
    print(" ".join(map(str, j)))

일단 위 코드도 정답이다. 하지만 굉장히 비효율적인 방식으로 푼 코드이다. 기본 조합에서 중복을 제거하여 리스트에 저장하고 그 값을 오름차순으로 만들어 출력한다. 참고로 아래 코드보다 4배 더 걸린다. 당연히 메모리 초과에 걸리리라 예상했는데 맞았다고해서 당황스러웠다. 졸면서 풀어서 그렇다..

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, sys.stdin.readline().split())
answer = []
ans = []

def back(start):
    if len(answer) == M:
        print(" ".join(map(str, answer)))
        return
    for i in range(start, N+1):
        if i not in answer:
            answer.append(i)
            back(i+1)
            answer.pop()

back(1)

사실 N과 M(1)을 풀었다면 매우 간단하게 풀 수 있다.
바로 back함수에 시작수를 인자로 주는 것. 값이 연속되지 않는 수로 했다면 시작 인덱스와 후보 값 배열 두 개를 인자로 줘야겠지만 그 보다 단순한 경우이므로 간단하게 시작 수를 줘서 해결이다.