[python 구름] 직사각형 만들기

📜 접근 방법

딕셔너리와 우선순위 큐를 사용

1. 딕셔너리로 입력 받은 갯수를 저장하면서 힙에도 저장한다.
2. pop하여 그 값의 갯수가 2개 이상인지 확인 후 pair에 저장한다. (우선순위 큐를 이용하여 제일 큰 수를 pop하기 때문에 정렬이 필요 없다.)
3. 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)

 

💡알게 된점