백준 2164(카드분류2) 문제풀이

📌문제 설명

백준 문제풀이

백준 2164 카드분류2 문제

입출력 결과

📌문제 접근 방식

첫 번째 시도

아무생각 없이 시도했다가 시간 초과가 떴다.

문제를 접근한 방식은 다음과 같았다.

1. 첫 번째 카드를 제거한다.

2. 두 번째 카드를 맨 뒤로 보낸다.

위 두 과정을 1장이 남을때까지 수행하면 되는 문제라고 생각했다.

따라서 리스트를 사용했고 맨 앞에 카드를 삭제하고 뒤로 보내도록 구현했다.

문제가 없을거라 생각했던 이유 두 가지이다.

1. 1중 for문을 사용했다.

2. 최대 가드 수가 50만장이다.

소스코드

# 2초 초과 - N 500000으로 대입 시 79초가 걸렸다.
# 병목 지점은 어디지?

import sys

n = int(sys.stdin.readline().rstrip())
cards = [x for x in range(1,n+1)]

def solution(cards):
    while len(cards) > 1:
        cards.pop(0)
        cards.append(cards.pop(0))
    print(cards[0])

solution(cards)

간과했던 부분

해당 로직이 Queue처럼 동작한다는 것을 알고도 리스트로 구현했다.

따라서 값을 넣고 빼는 과정에서 굉장한 성능 저하가 일어났다.

리스트와 큐의 성능차이가 나는 이유에 대해 더 깊게 공부해 볼 필요성을 느꼈다.

📌문제 풀이

다시 큐로 구현하니 매우 잘 동작했다.

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
cards = [x for x in range(1,n+1)]
cards = deque(cards)

def solution(cards):
    while len(cards) > 1:
        cards.popleft()
        cards.append(cards.popleft())
    print(cards[0])

solution(cards)

 

📌성능 차이

2021-03-12

리스트로 큐를 구현 시 성능 차이가 나는 이유에 대해 추가적으로 공부해보았습니다.

Queue

큐는 영화관 매표소에 줄을 서는 구조와 같습니다.

먼저 줄을 선 사람이 우선적으로 표를 살 수 있는 것이죠.

새로운 사람이 들어오면 맨 뒤에 줄을 서야 합니다.

이것을 파이썬에서는 리스트로 구현이 가능합니다.

list 함수의 append()와 pop(0)를 사용하면 큐처럼 동작하도록 만들 수 있습니다.

List 단점

하지만 파이썬에서는 Queue 자료구조를 따로 제공을 하고 있습니다.

또한 collections 라이브러리 안에 deque 자료구조를 제공합니다.

이유가 무엇일까요?

List의 경우 맨 뒤에서 append하고 pop할 때는 시간 복잡도가 O(1)이 듭니다.

하지만 맨 앞에서 넣고 빼고 할 경우 O(N)으로 증가하게 됩니다.

그 이유는 하나를 제거할 경우 비어있는 만큼 이동을 시켜줘야하기 때문입니다.

Deque

Deque의 경우 append() 함수와 popleft() 함수로 사용하여 큐처럼 동작하게 만들 수 있습니다.