문제
지호는 매일 아이스크림 가게에 방문한다. 아이스크림을 먹던 지호는 놀라 자빠질 수밖에 없었다. 실수로 민트초코 맛을 먹었기 때문이다. 대다수의 사람은 치약 맛이 난다는 이유로 민트초코를 싫어한다. 아이스크림으로 이를 닦는다는 발상은 누가 한 것인지 궁금할 뿐이다. 아무튼 매번 아이스크림을 사 먹는 것이 지겨워진 지호는 이제부터 아이스크림을 훔쳐 먹기로 결심하였다.
아이스크림 가게에는 다양한 맛의 아이스크림 N개가 한 줄로 배치되어 있다. 아이스크림에는 번호가 매겨져 있는데, 가장 왼쪽 아이스크림이 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 아이스크림은 N번이다. 지호는 항상 양이 가장 많은 아이스크림을 선택하여 전부 먹는다. 양이 가장 많은 아이스크림이 여러 개라면 가장 왼쪽에 있는 것을 먹는다.
지호는 대다수의 사람과 마찬가지로 민트초코 맛을 싫어한다. 다행히 지호는 아이스크림의 양이 주어질 때 아이스크림의 맛을 알 수 있다. 지호의 판별법에 따르면, 아이스크림의 양이 7의 배수라면 민트초코 맛이고, 그렇지 않다면 민트초코 맛이 아니라고 한다.
지호는 민트초코를 싫어한다는 사실을 명심하라. 민트초코 맛 아이스크림을 먹은 지호는 크게 분노하여 남아 있는 아이스크림의 순서를 좌우로 뒤집는다. 즉, K개의 아이스크림이 있다면 i번째 아이스크림과 (K - i + 1)번째 아이스크림의 위치를 뒤바꾼다. (1 ≤ i ≤ ⌊K / 2⌋)
지호는 N개의 아이스크림 중 M개의 아이스크림을 먹으려 한다. 아이스크림의 양이 주어졌을 때, 지호가 먹은 아이스크림의 번호를 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 전체 아이스크림의 개수 N과 지호가 먹을 아이스크림의 개수 M이 주어진다.
두 번째 줄에 N개의 정수 , , ..., 이 주어진다. 이때 는 번 아이스크림의 양을 의미한다.
모든 입력은 공백으로 구분되어 주어진다.
출력
M개의 줄에 걸쳐 i(1 ≤ i ≤ M)번째 줄에는 지호가 i번째로 먹은 아이스크림의 번호를 출력한다.
소스코드
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
ice = list(map(int, input().split())) # 아이스크림 양 입력 받기
idx = dict() # 각 아이스크림의 인덱스 저장
for i in range(n): # {아이스크림 양: [index]} 형태로 저장
if idx.get(ice[i]) is None:
idx[ice[i]] = deque([i + 1]) # pop을 빠르게 하기 위해 deque로 저장
else:
idx[ice[i]].append(i + 1)
isReversed = False
ice.sort(reverse=True) # 내림차순 정렬
dq = deque(ice) # ice를 deque로 변경
result = [] # 결과 저장
while m > 0:
mValue = dq.popleft() # 양이 가장 많은 아이스크림
if isReversed: # 순서가 뒤집혔는지 여부
index = idx[mValue].pop() # 순서가 뒤집혔다면 맨 마지막 index pop
else:
index = idx[mValue].popleft() # 뒤집히지 않았다면 맨 처음 index pop
if mValue % 7 == 0 and isReversed: # 양이 7의 배수인 아이스크림을 먹은 경우
isReversed = False
elif mValue % 7 == 0 and not isReversed:
isReversed = True
result.append(index)
m -= 1
for i in result:
print(i)딕셔너리에 각 아이스크림의 양과 그 index를 deque로 저장하여 index를 O(1) 시간 안에 접근할 수 있도록 하였습니다. 그리고 만약 순서가 뒤집혀있다면 index deque의 맨 뒤에서, 그렇지 않다면 맨 앞에서 index를 가져오도록 하였습니다.
pop 연산을 여러 번 수행해야 하기 때문에 pop 연산이 빈번하게 일어나는 곳에 deque를 사용했습니다. (list는 특정 위치의 값을 삭제할 때 O(n)의 시간이 걸리지만, deque의 pop과 popleft는 모두 O(1)이기 때문입니다.)
