파이썬(알고리즘) :: m번째 숫자를 제거할때, 최종적으로 남은 숫자 반환(큐 문제)

이번에는 알고리즘 유형 중 하나인 큐 유형에 대하여 정리 해보려고 한다.

 

문제 유형으로는 숫자로 이루어진 문자열과 임의의 숫자 m을 입력 받은 후 문자열에서 1부터 m 까지 카운트 하며, 차례대로 배열 뒤로 배치 후, m번째 있는 숫자를 제거하는 과정을 반복 수행하여 최종적으로 남은 숫자를 반환하는 문제이다.

 

아래 그림은 1 부터 8까지 숫자들을 정렬 후, 3번째에 위치한 숫자들을 차례대로 제거하는 로직이다.

# 풀이 과정

큐는 자료구조는 FIFO(First in First out) 구조를 가지고 있기 때문에 리스트의 가장 앞에 있는 인덱스 부터 제거하는 해당 문제 유형에서 적용하기 알맞다.

 

파이썬에서는 deque라는 모듈을 지원하기 때문에 리스트 앞에 있는 인덱스를 제거할때는 popleft( ) 모듈을 사용하고,

제거한 숫자를 리스트 가장 뒤에 붙일때는 append( )를 사용하여 해당 과정을 반복한다.

 

** deque(double ended que) : 스택과 큐의 기능을 가진 객체, 양방향으로 큐

 

# 풀이 

from collections import deque

def check(input, m):
    num_list = list(map(int, input.split()))
    que      = deque(num_list)

    while True:
        for i in range(1, m+1):
            if i == m: 
                que.popleft()   
            else:
                temp = que.popleft()
                que.append(temp)

        if len(que) == 1: return que[0]

input1 = "1 2 3 4 5 6 7 8"
m = 3

print(check(input1, m))

# 실행 결과

7