[백준/알고리즘/python/java] 2164번 - 카드2

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

맨 처음에 시간초과가 났던 코드였다. 심지어 PyPy3로도 시간초과가 났었다.

로직은 단순한데, 시간초과가 났다면 다른 라이브러리의 힘을 빌려야 하는 순간이다.

기존 리스트로 카드 세트를 생성하고 처음엔 remove나 del 함수를 사용했지만, 단순히 pop 함수를 사용해도 되는데, 

파이썬의 list는 중간에 있는 요소를 pop할 때 시간복잡도가 O(n)이지만,

collections.deque는 시간복잡도가 O(1) 라고 한다. 

 

먼저 맨 처음에 작성했던 코드는 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input())
card_list = []

for i in range(n, 0, -1):
    card_list.append(i)

while(len(card_list) != 1):
    del(card_list[-1])
    temp = card_list[-1]
    card_list.insert(0, temp)
    del(card_list[-1])

print(card_list[0])

list.remove(찾을 아이템)와 del(list[인덱스값]) 도 맨 처음엔 잘못 활용했고, 처음 코드는 시간초과뿐만 아니라 단순한 로직에 반해, 너무 투박했다. 

 

collections라는 라이브러리에 있는 deque에 대해서 알아본 다음 작성한 코드는 다음과 같다.

import sys
import collections
input = sys.stdin.readline


n = int(input())
card_list = collections.deque([i for i in range(n, 0, -1)])


while(len(card_list) != 1):
    del(card_list[-1])
    temp = card_list[-1]
    card_list.insert(0, temp)
    del(card_list[-1])

print(card_list[0])

카드 리스트를 생성하는데, list가 아니라 deque만 써줘도 시간초과 문제는 해결할 수 있었다. 여기서 코드를 더 줄일 수 있다. deque를 사용했으면, 그에 따른 함수도 사용해야 더 효율적일 것이다.

마지막으로 작성한 코드는 아래와 같다.

import sys
import collections
input = sys.stdin.readline


n = int(input())
card_list = collections.deque([i for i in range(1, n+1)])


while(len(card_list) != 1):
    card_list.popleft()
    card_list.rotate(-1)


print(card_list[0])

확실히 보기에도 더 간결해졌고, 속도도 더 줄일 수 있었다.

deque에는 list.pop(0)과 같은 기능을 하는 deque.popleft()라는 기능이 있었다.

그리고 append와 pop(0) 두 개를 쓸 필요없이 (insert와 remove 두 개를 쓸 필요 없이)

그냥 deque.rotate(양수or음수)라는 함수를 쓰면 됐다.

 

deque.rotate(num)은 데크를 num만큼 회전한다는 뜻이다. (양수면 오른쪽, 음수면 왼쪽).

이외에도 collections의 deque기능에는 재미있는 것들이 많았다.

queue은 queue와 stack의 합친 형태라고 생각해도 된다. 양방향으로 삽입과 삭제가 가능하니 애용하면 무척 편한 자료구조일 것이다.

아래는 deque의 주요 기능들이다.

 

deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.

deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.

deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.

deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.

deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.

deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.

deque.remove(item): item을 데크에서 찾아 삭제한다.

deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

 

이 외에도 자바로 처음 코딩을 배워서 그런지, 파이썬에서 리스트를 만들 때 바로 for문을 활용하는 형식에 아직은 익숙치 않은데, 이런 습관도 어서 익숙하게 내 것으로 만들어야 겠다는 생각이 들었다.

([i for i in range(n, 0, -1)]) 이런 것 말이다.

enumerate를 활용하는 for문도 셀레니움 할 때 해봤던 게 기억이 난다. (인덱스,value값) 

여튼 이런 파이썬만의 기능등을 많이 써봄으로써 익숙해져야 할 것 같다.