N과M 12


파이썬 문제를 푼지 얼마 되지 않았을 때, 굉장히 힘들었던 N과M 문제들이다. 어제 오늘 12개의 문제들을 모두 다 풀었는데, 처음 풀때와는 달리 비교적 수월하게 풀 수 있었다. 마지막 11, 12번에서 중복을 제거하는 부분을 비교적 많이 고민해서 포스팅하게 되었다.

주어진 N개의 자연수들 중 M개를 고르는 문제이다. 같은 수를 여러번 골라도 되며, 다음 숫자는 이전의 숫자보다 같거나 커야한다.

  • 같은 수를 여러번 골라도 되지만, 같은 수열을 여러번 출력하면 안된다!


같은 수열을 여러번 출력하지 않기 위해 처음 생각했던 방법은 M개 길이의 문자들을 리스트에 저장해 놓고, 출력하기 전에 이미 출력했는지 검사하는 방법이다. 하지만, 이렇게 되면 출력하기 전 리스트에서 일일이 비교해야 한다는 단점이 있다.


  • 이를 해결하기 위한 첫 번째 방법은 재귀함수로 인자를 넘기기 전, 애초에 중복을 제거해주는 방법이다.
def Comb(x,cnt,save):
    if cnt == m:
        print(save)
        return
    before = -1
    for i in range(x,n):
        #num[i]가 이전 값과 다를 때만 재귀함수 통과
        if num[i] == before:
            continue
        Comb(i,cnt+1,save+str(num[i])+" ")
        before = num[i]

num에는 n개의 숫자들을 입력받았고, 정렬되어있는 상태이다. 따라서, 크기가 같은 숫자들은 서로 인접해 있다. before라는 인자를 활용해 같은 숫자들에 대해서는 두번 이상 재귀함수로 들어가지 못하게 했다.


CODE - 중복 제거

import sys
read=sys.stdin.readline

n,m=map(int,read().split())
num = list(map(int,read().split()))
num.sort()

def Comb(x,cnt,save):
    if cnt == m:
        print(save)
        return
    before = -1
    for i in range(x,n):
        if num[i] == before:
            continue
        Comb(i,cnt+1,save+str(num[i])+" ")
        before = num[i]

Comb(0,0,"")


  • 두 번째 방법은 이미 출력했는지 검사를 할 때, 리스트를 사용하는 것이 아니라 집합 자료구조를 사용하는 것이다.

list 혹은 Tuple 자료구조에서 특정 Element가 있는지 확인하는 작업의 시간복잡도는 O(N)인 반면, set 자료구조에서는 시간복잡도가 O(1)이다.


CODE - set 활용

import sys
read=sys.stdin.readline

n,m = map(int,read().split())
NUM=list(map(int,read().split()))
#NUM내의 중복된 숫자 제거
NUM=list(set(NUM))
NUM.sort()
n=len(NUM)

check = set()

def Comb(x, cnt , save):
    if cnt == m:
        save_t = tuple(save)
        #이미 출력된적이 있는 값이라면 다시 출력하지 않는다.
        if save_t not in check:
            check.add(save_t)
            print(save)
        return
    for i in range(x, n):
        Comb(i,cnt+1,save+str(NUM[i])+" ")
Comb(0,0,"")


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]