[프로그래머스/Python] 카드 뭉치

문제

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

프로그래머스

각 카드 뭉치 중 맨 앞의 카드만 사용하여 goal을 만들 수 있으면 Yes 리턴, 아니면 No 리턴

---

1. deque() 라이브러리

from collections import deque

deque()를 이용하여 스택과 큐처럼 이용할 수 있다.

 

deque() 생성

queue = deque()

queue = deque([1,2,3,4,5])

 

deque() 함수

.appendleft(x) 맨 앞 추가

.popleft() 맨 앞 삭제

.append(x) 맨 뒤 추가

.pop() 맨 뒤 삭제

 

https://wikidocs.net/104977

008 앞뒤에서 자료를 넣고 빼려면? ― collections.deque

 

맨 뒤에 추가하고 삭제하기

deque: append(x) 와 pop()

list: append(x) 와 pop()

시간복잡도 동일 O(1)

 

맨 앞에 추가하고 삭제하기

deque: appendleft(x), popleft()

list: insert(0, x) 와 pop(0)

시간복잡도 O(1), O(n)

 

데크와 리스트의 시간복잡도

https://wellsw.tistory.com/122

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)

 

 

카드뭉치의 맨 앞을 보고, 삭제하기 위해서 시간이 덜 걸리는 deque() 사용

인덱스 에러를 방지하기 위해 cards1 cards2안에 적어도 하나의 문자열은 들어있도록 함( 카드 길이가 2이상일 때만 popleft() )

from collections import deque
def solution(cards1, cards2, goal):
    cards1 = deque(cards1)
    cards2 = deque(cards2)
    answer = ''
    #goal을 돌면서 cards1 제일 앞에 있는지 본다
    for i in goal:
        if i != cards1[0] and i != cards2[0]:
                return "No"
        if i == cards1[0]:
            if len(cards1)>1:
                cards1.popleft()
        if i == cards2[0]:
            if len(cards2)>1:
                cards2.popleft()

    return "Yes"