[BOJ 20956, Python 3] 아이스크림 도둑 지호

https://www.acmicpc.net/problem/20956

20956번: 아이스크림 도둑 지호

 

 

풀이

아이스크림의 양이 가장 많은 것부터 먹으면서 7의 배수 양을 가진 아이스크림을 먹을 경우, 아이스크림 먹는 순서를 뒤집는다고 합니다.

 

이건 생각해보면 딕셔너리 말고는 답이 안보입니다. 딕셔너리는 dict[아이스크림 양] = [1, 3, 5, 6] 이렇게 key값을 아이스크림 양으로 저장하고, value값은 아이스크림 먹는 번호를 저장하면 됩니다.

이때 key값은 in을 사용하면 시간이 오래 걸릴 수도 있으니 defaultdict를 사용하고, value에 쓰일 자료구조는 원소를 앞에서 빼는 경우도 있고, 뒤에서 빼는 경우도 있으므로 deque를 사용하면 됩니다.

 

이렇게 딕셔너리에 값을 저장해주고, key값을 기준으로 내림차순 정렬하여 문제에서 요구한대로 구현해주면 됩니다.

 

 

코드

input = __import__('sys').stdin.readline
n, m = map(int, input().split())
a = [*map(int, input().split())]
dfd = __import__('collections').defaultdict(lambda: __import__('collections').deque())
for i in range(n):
    dfd[a[i]].append(i+1)
reverse = 0
val = 0
for x in sorted(dfd.keys())[::-1]:
    while dfd[x]:
        if not reverse: print(dfd[x].popleft())
        else:print(dfd[x].pop())
        if x % 7 == 0: reverse ^= 1
        val += 1
        if val == m: exit()