백준 2164. 카드 2

·2021년 3월 6일
0

알고리즘

목록 보기
6/20

백준 2164번 카드2 문제

TRYS AND INSIGHTS

  • list에서 pop(0)의 연산이 O(n)이라고 함.

  • 그래서 python 공식 docs에서도 리스트는 큐로 쓰는 걸 권장하지 않는다고 함. 차라리 collections의 deque을 쓰라고 함.

  • deque

    • popleft, pop

    • append, appendleft

      나머지 extend, extendleft, rotate은 O(k)의 시간 복잡도를 가짐
      remove는 O(n)의 시간 복잡도를 가짐

[1번 시도]

마지막 한 장 남았으면 어차피 맨 뒤로 보내므로 그냥 return해 버리기의 의도
cards.popleft() 다음으로 len(cards)==1을 검사해서 return해 주었으나,
N = 1의 경우 그렇게 되면 while문에서 영원히 못 빠져나와서 런타임에러 생김.

[2번 시도]

N = 1의 경우를 따로 빼 줌.

SOLUTION

from collections import deque

def main():
    N = int(input())
    cards = deque(range(1, N+1))
    if N == 1:
        return 1
    while(True):
        
        # 맨 앞 장 바닥에 버리기
        cards.popleft()
        
        if len(cards) == 1:
            return cards.pop()
            
        # 다음 앞 장 맨 뒤로 보내버리기
        top = cards.popleft()
        cards.append(top)       
    

print(main())
profile
이것저것 개발하는 것 좋아하지만 서버 개발이 제일 좋더라구요..

0개의 댓글