💡 백준 2346:
덱 기본 구조 활용
🌱 코드 in Python
알고리즘: Deque
import sys
n = int(sys.stdin.readline())
data = list(enumerate((map(int, sys.stdin.readline().split())), start = 1)) # (인덱스, 값) 구조로 저장
idx = 0 # 첫번째 idx 고정
while data: # data가 존재하는 동안
ret = data.pop(idx) # 추출 값
print(ret[0], end=' ') # 인덱스 출력
if ret[1] < 0 and data: # 다음 인덱스 위치가 음수면
idx = (idx + ret[1]) % len(data) # 왼쪽으로
elif ret[1] > 0 and data: # 다음 인덱스 위치가 양수면
idx = (idx + (ret[1] - 1)) % len(data) # pop한 1덱스 하나 제외 후 오른쪽으로이번 문제는 덱의 기본 구조를 이용하되, pop_front or pop_back되어 바뀐 인덱스와 관계없이 원 인덱스를 출력하는 것이 중요한 문제였다
enumerate를 활용하여 인덱스 값을 같이 저장하는 list 사용 시 그 부분을 해결할 수 있다
현재 풍선이 가지고 있는 값에 따라 다음 인덱스가 결정되는데 이는 mod 연산을 통해 얻을 수 있다
두번째로는 list가 아닌 deque 모듈을 활용해서도 문제를 해결할 수 있다
import sys
from collections import deque
n = int(sys.stdin.readline())
deq = deque(enumerate(map(int, sys.stdin.readline().split()), start=1))
for i in range(n):
p = deq.popleft() # pop(0)과 같은 결과를 가져오지만, pop(0)보다 더 빠르다
print(p[0], end=' ')
if p[1] > 0:
deq.rotate(-(p[1] - 1)) # popleft된 1칸을 제외하고 시계 반대방향으로 회전
else:
deq.rotate(-p[1]) # 시계 방향으로 회전위 코드는 deque 자료구조를 제대로 활용하는 방법이 아닐까!
첫번째처럼 list를 활용할 경우 실제 index에 따라 배열을 수정하고 탐색한다면,
두번째 코드는 deque 자료구조의 front, rear의 조정을 통해 실제 index는 변경되지 않는다
만약 front가 1인 상태에서 rotate(-1) 연산을 한다면 front는 0이 될 것이고
이 상태에서 popleft를 할 시 0번째 index에 있는 값이 바로 삭제 되면서 front는 다시 1이 될 것이다
이때 실제 자료들이 저장된 위치가 바뀌는 것이 아니라 front가 가리키는 index만 바뀌게 된다
반면에 배열의 경우 pop(0)을 할 시, 0번째 index에 있는 값을 삭제 후 그 이후에 있는 값을 전부 한 칸씩 앞으로 이동시켜 배열을 재조정해주어야 한다
따라서 deque.popleft()의 경우 시간 복잡도가 O(1)이지만, list를 활용 시 O(n)의 시간복잡도를 갖게 되는 것이다
그러나 deque의 경우 index를 통한 접근이 불가능하기 때문에 중간에 있는 값에 접근이 필요할 경우 list를 사용하는 것이 더 효율적이다
또한 rotate 함수는 양수 입력 시 시계 방향(배열 왼쪽)으로 자료를 회전시키며, 음수 입력 시 반시계 방향(배열 오른쪽)으로 자료를 회전 시킨다
🧠 기억하자
- 모듈러 연산
- 파이썬의 모듈러 연산이 c와 달라 처음에는 위와 같은 인덱스 계산을 하지 못했는데, 또 새로운 방법을 알게 되었다
- 자세한 차이는 https://lecor.tistory.com/16 이 사이트에서 확인! 정리가 잘 되어있다
- enumerate
- index와 함께 튜플 형태로 list를 만들어 준다
- 이걸 몰라서 딕셔너리 자료형 썼다가 value error를 쳐맞아따... 그치,, 중복 값이 들어올 수 있는데 딕셔너리라니요 ㅠ
- rotate
- deque.rotate(-1), deque.rotate(1)에 대해 잘 알아두자!
아래는 망한 코드 대공개 😢
import sys
n = int(sys.stdin.readline())
d = list(map(int, sys.stdin.readline().split()))
d_t = {0:0}
for i in range(n): # 도저히 index와 함께 튜플로 만드는 방법을 몰라 멍청한 짓 시전 enum을 잘 활용하자
d_t[d[i]] = i + 1
ret = []
next_idx = d[0]
for i in range(n):
cur_idx = d.index(next_idx)
value = d[cur_idx]
ret.append(d_t.get(value))
if value > 0:
next_idx = d[(cur_idx + value) % len(d)]
else:
if cur_idx + value >= 0:
next_idx = d[cur_idx + value] # 음수도 mod 연산에 의해 정확한 값을 얻을 수 있다는 걸 몰랐지 모여?!
else:
next_idx = d[len(d) + value + cur_idx]
del d[cur_idx]
for r in ret:
print(r, end=' ')