📜 접근 방법
딕셔너리와 우선순위 큐를 사용
- 딕셔너리로 입력 받은 갯수를 저장하면서 힙에도 저장한다.
- pop하여 그 값의 갯수가 2개 이상인지 확인 후 pair에 저장한다. (우선순위 큐를 이용하여 제일 큰 수를 pop하기 때문에 정렬이 필요 없다.)
- pair에 순서대로 2개의 값을 곱해서 넓이를 만들고 res에 더한다.
❌ 실패 코드
만들수 있는 모든 직사각형의 최대 수를 구해야하는데 제일 큰 하나의 직사각형만 구함
from heapq import heappop, heappush
import sys
n = int(input())
nums = list(map(int, input().split()))
dict_ = {}
nums_dict = {}
heap = []
res = 1
cnt = 0
for num in nums:
if dict_[num] not in dict_:
dict_[num] = 1
if num not in nums_dict:
nums_dict[num] = 1
else:
dict_[num] += 1
nums_dict[num] += 1
heappush(heap, -num)
while heap:
tmp = heappop()
if dict_[tmp] >= 2:
tmp = -heappop(heap)
if nums_dict[tmp] >= 2:
print(tmp)
heappop(heap)
res *= tmp
cnt += 1
if cnt == 2:
break
print(res)
if res == 1:
print(0)
else:
print(res)
✅ 정답 코드
from heapq import heappop, heappush
import sys
n = int(input())
nums = list(map(int, input().split()))
nums_dict = {}
heap = []
pair = []
res = 0
for num in nums:
if num not in nums_dict:
nums_dict[num] = 1
else:
nums_dict[num] += 1
heappush(heap, -num)
while heap:
tmp = -heappop(heap)
if nums_dict[tmp] >= 2:
heappop(heap)
pair.append(tmp)
nums_dict[tmp] -= 2
for i in range(0, len(pair) // 2 * 2, 2):
res += pair[i] * pair[i + 1]
print(res)
💡알게 된점
'코딩테스트 > Python' 카테고리의 다른 글
[python 구름] 피보나치 수 (0) | 2023.05.21 |
---|---|
[python 구름] 구름 스퀘어 (0) | 2023.05.20 |
[python 구름] 거스름돈 (0) | 2023.05.17 |
[python 구름] 1차원 뿌요뿌요 (0) | 2023.05.16 |
[python 구름] 체크 카드 (0) | 2023.05.15 |