2164. 카드2 (silver IV)

✔️ 문제

2164번 문제 보기

✔️ 문제 분석 및 해결 과정 설계

• 1 <= N <= 500,000 N의 값이 꽤 크기에 시간복잡도를 고려할 것

ex) N = 6
[2, 3, 4, 5, 6]
[3, 4, 5, 6, 2]
[4, 5, 6, 2]
[5, 6, 2, 4]
[2, 4, 6]
[6, 4]
[4]

1번 과정. 맨 앞의 값을 삭제(삭제)
2번 과정. 맨 앞의 값(삭제)을 맨 뒤로 보내기(삽입)

자료구조 선택의 과정

1. 배열로 접근
   배열에서의 삽입/삭제 : $O(N)$
   → 만약 하나의 값이 삽입 or 삭제되었다면 인덱스를 채우기 위해 N-1 번의 자리 이동 필요

• 하나의 원소가 남을 때까지 반복 : $N-1$
• 삭제 2회(1, 2번 과정) + 삽입 1회(2번 과정) = $3 * N$
  → 배열에서의 시간복잡도 : $O((N-1) * 3N)$ → $O(N^2)$
  : 배열을 사용할 경우 시간 초과가 발생

2. 큐로 접근
   큐에서의 삽입/삭제 : $O(1)$
   → 만약 하나의 값이 삽입 or 삭제되었다면 인덱스를 채우기 위해 N-1 번의 자리 이동 필요

• 하나의 원소가 남을 때까지 반복 : $N-1$
• 삭제 2회(1, 2번 과정) + 삽입 1회(2번 과정) = $3 * 1$
  → 배열에서의 시간복잡도 : $O((N-1) * 3)$ → $O(N)$
  : 큐 사용

✔️ 문제 해결 과정

1. 차례로 deque에 값을 넣기

from collections import deque

dq = deque()
N = int(input())
for i in range(1, N+1):
    dq.append(i)

• 선언과 동시에 값을 넣어줄 수 있는 방법

from collections import deque

N = int(input())
dq = deque(range(1, N+1))

2. 가장 앞의 값을 삭제

from collections import deque

dq = deque()
N = int(input())
for i in range(1, N+1):
    dq.append(i)

while len(dq) > 1:
    dq.popleft()

• deque 가장 왼쪽의 원소 값을 제거 : dq.popleft()
  • cf. dq.pop()

3. 삭제 후 남은 가장 앞의 값을 가장 뒤로 보냄(삽입)

from collections import deque

dq = deque()
N = int(input())
for i in range(1, N+1):
    dq.append(i)

while len(dq) > 1:
    dq.popleft()
    dq.append(dq.popleft())

print(dq.popleft())

• dq.append()의 인자로 가장 앞 원소를 삭제하는 동시에 리턴하는 dq.popleft()를 넣어줌
• 마지막 남은 원소를 보여줄 때에는 deque의 가장 앞에 남은, dq.popleft()의 리턴 값을 출력

Ⅹ 배열로 문제를 풀이할 경우

N = int(input())
arr = []

for i in range(1, N+1):
    arr.append(i)

while len(arr) > 1:
    arr.pop(0)
    arr.append(arr.pop(0))

print(arr.pop())

• 코드 간소화 ver.

N = int(input())
arr = [*range(1, N+1)]

while len(arr) > 1:
    arr.pop(0)
    arr.append(arr.pop(0))

print(arr.pop())

• N의 최대 값인 500,000을 입력할 경우 시간 초과 발생

💡 회고

전날 풀었던 9012번을 바탕으로 문제 풀이에 적합한 자료구조 선정 & 시간복잡도의 고려를 1순위로 두고 문제를 해결했다.
알고리즘 준비를 거진 몇년만에 해서 감이라는게 하나도 없었는데 맞아서 기분이 아주 좋았다 ... 😆

큐를 사용해 코드를 작성할 때, 본인은 dq.append(dq[0])으로 풀이하였으나 자료구조로 큐를 사용한다는 점에서
적합한 코드 작성은 아니었다고 판단된다.
→ 인덱스로 접근하는 것은 큐보다는 배열 자료구조에 적합하다고 볼 수 있으며,

dq.append(dq[0])
dq.popleft()

코드를 위와 같이 삽입한 뒤 삭제하는 로직으로 구현하였기에 가독성 측면에서 좋다고 판단되지는 않기 때문이다.

deque에서 사용할 수 있는 함수에 대한 지식이 없다.
python에서 자료구조별로 사용할 수 있는 메소드와 인스턴스를 확인하고 암기해
검색이 불가능한 환경에서도 문제풀이가 가능하도록 연습이 필요할 것 같다.