[G4] 백준 14698번 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) C++ 우선순위 큐

리뷰

 

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

C++로 푸려고 시도했는데 큐 내부 요소가 long long을 초과하는 경우 처리가 안떠올라서 그냥 파이썬으로 풀었다.

 

 

함수

없음

 

 

문제풀이

1. t에 테스트 케이스 개수를 받아주고, t번의 for문을 수행해 준다.
2. 매 테스트 케이스 마다 n에 요소의 개수, lst에 배열 정보를 입력 받는다.
3. lst를 heapq객체로 만들어 준 뒤 빈 리스트 arr을 초기화 해준다.
4. 무한 루프를 수행하고, 힙에서 요소를 하나 빼내 변수 one에 저장해준다.
5. 만약 lst가 비었을 경우 break처리해 준다, 아니라면 요소를 하나 더 빼내 변수 two에 저장해준다.
6. arr과 lst에 one * two값을 추가해 준다.
7. while 루프가 중료된 경우 변수 ans를 1로 초기화 하고, arr에 있는 값을 모두 곱해준다.
8. ans를 1000000007로 나눈 나머지를 출력해 준다.

 

트러블 슈팅

1. C++제출 시 정해를 구할 때 큐 내부 값이 long long 범위를 넘어서는데 이를 해결하진 못했다.
2. 파이썬으로 로직을 만들어 제출하여 AC를 받았다.

 

참고 사항

• 아마 문자열로 직접 구현해 주면 가능할 듯 한데... 그냥 이런 문제는 파이썬으로 푸는게 속 편할듯 하다.

 

정답 코드

import heapq
import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    lst = list(map(int, sys.stdin.readline().split()))
    heapq.heapify(lst)
    arr = []

    while 1:
        one = heapq.heappop(lst)
        if not lst: break
        two = heapq.heappop(lst)
        arr.append(one * two)
        heapq.heappush(lst, one * two)

    ans = 1
    for i in arr:
        ans *= i
    print(ans % 1000000007)