N개의 연속된 자연수 리스트에서 인접하지 않은 m개 뽑기

From N consecutive lists of natural numbers, pick m that are not adjacent.

 

코딩테스트 대비를 위해 Heap / Queue / Stack의 선형 자료구조 문제를 풀다 보면 대부분은 0번째와 마지막 인덱스만의 예외 처리로 해결되는 경우가 많다.

문제를 풀면서 많이 나오는 듯한 느낌인데, 비슷한 유형의 예외처리가 쉽지 않아 공유해보고자 포스팅하게 되었다.

[1,2,3,4,5,6,7] 과 같이 연속된 N개의 자연수에서 m개를 뽑을 때 연속된 자연수가 없는 경우만 뽑아내기

 

여러번 등장하는 알고리즘인 것 같은데, 생각보다 해결하기가 쉽지 않아 해당 주제에 대해 여러번 고민하다 문제를 해결했다.

from collections import deque
from itertools import combinations

def drop_adjacent(N,m):
    combs = list(combinations([i for i in range(1, N+1)], m))
    res = []
    for li in combs:
        queue = deque(li)
        
        while queue:
            q = queue.popleft()
            if q+1 in queue:
                break
            
            if len(queue)==0:
                res.append(li)
    return res

 

Loop 안의 Loop를 예외 처리하면 쉽게 해결될 것이라 생각했지만, 예외가 생각보다 많았다.

더군다나 최근 자료구조 및 알고리즘을 공부하는데, for문의 중첩은 좋지 않음을 인지하다 보니 while문을 통한 처리를 고안하게 되었다.

배우고 있는 선형 자료구조를 최대한 활용하고자 collections 패키지의 deque를 이용했지만, 그냥 list를 이용한 pop while문으로도 충분할 듯 하다.