[프로그래머스] deque을 활용한 문제 풀이

deque는 양방향 자료구조로써 한쪽으로만 데이터를 넣고 뺄 수 있는 리스트와 다르게 앞 뒤에서 데이터를 넣고 뺄 수 있는 자료구조입니다. Python에는 from collections import deque을 통해 deque 자료구조를 생성할 수 있습니다. 이번 글에서는 deque을 활용해 해결할 수 있는 문제들을 풀어보겠습니다.

 

1. 공 던지기

https://school.programmers.co.kr/learn/courses/30/lessons/120843

프로그래머스

공 던지기 게임 룰은 1번부터 던지면서 오른쪽으로 한 명을 건너뛰고 그다음 사람에게만 던질 수 있다는 것입니다. 정수 배열과 정수 K가 주어졌을 때 K번째로 공을 던지는 사람의 번호를 출력해야 합니다.

 

Test Case 1. numbers = [1, 2, 3, 4] K = 2

첫번째 : 1번이 3번에게 공 던지기

두 번째 : 3번이 1번에게 공 던지기

따라서 2번째로 공을 던지는 사람의 번호는 3번

 

Test Case 2. numbers = [1, 2, 3, 4, 5, 6] K = 5

첫 번째 : 1번이 3번에게 공 던지기

두 번째 : 3번이 5번에게 공 던지기

세 번째 : 5번이 1번에게 공 던지기

네 번째 : 1번이 3번에게 공 던지기

다섯 번째 : 3번이 5번에게 공 던지기

따라서 5번째로 공을 던지는 사람의 번호는 3번

 

Solution)

입력받은 정수 배열을 deque로 생성하여 공을 던진 사람, 룰에 의한 건너뛰어진 사람이 연속적으로 뒤 순서로 연결되도록 하기

Test case 1.

1

2

3

4

 

3

4

1

2

 

배열의 앞 2명을 꺼낸 후 뒤쪽에다가 순서대로 붙이기 => deque의 popleft와 append 활용

from collections import deque

def solution(numbers, k):
    answer = 0
    nums = deque(numbers)

    while k!=1:
        for x in range(2):
            nums.append(nums.popleft())
        k -= 1

    answer = nums[0]
    return answer

 

2. 문자열 계산하기

https://school.programmers.co.kr/learn/courses/30/lessons/120902

프로그래머스

 

문자열로 입력된 수식을 계산하는 문제

가장 중요한 조건은 계산 결과는 항상 1 이상 100,000인 이하인 자연수

 

Test Case 1. "3 + 4"

answer = 7

 

Test Case 2. "100 - 101:

answer = 1

 

Solution)

입력된 문자열에서 공백을 없앤 후, 숫자는 deque에 연산자는 리스트에 넣기

=> 숫자는 먼저 입력된 순서대로 계산되어야 올바른 값이 나온다.

만약 숫자를 리스트에 넣는다면, "5 - 2"는 2가 먼저 나와서 (5 - 2)가 아니라 (2 - 5)로 계산된다.

from collections import deque

def solution(my_string):
    answer = 0
    my_string = my_string.strip().split(' ')
    num, operator = deque(), []
    answer = 0

    for x in my_string:
        try:   #입력된 문자열에서 숫자를 int형으로 변환 후 list에 삽입
            num.append(int(x))
        except ValueError as m:
            operator.append(x)

    while len(num) != 0:
        answer = num.popleft()  #먼저 입력된 순서대로 deque에서 빼기
        for y in operator:
            if y == '-':
                answer = answer - num.popleft()
            else:
                answer = answer + num.popleft()

    #계산한 값은 1이상 100000이하이다
    if answer < 0:
        answer = 1
    elif answer > 100000:
        answer = 100000
    return answer