우선순위 큐7 [python 구름] 직사각형 만들기 📜 접근 방법 딕셔너리와 우선순위 큐를 사용 딕셔너리로 입력 받은 갯수를 저장하면서 힙에도 저장한다. 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.. 2023. 5. 19. [python 구름] 0커플 📜 접근 방법 짝수인 n이 주어지며, n만큼 숫자가 들어오는데 짝이 아닐 경우 그 숫자를 더해야한다. 짝일 경우는 두 수를 더했을 시 0이 되어야한다. 우선순위 큐를 사용했고, 두 수를 더했을 때 0이면 결국 -k 와 k를 더했을 경우 0이 되기에 2개의 힙을 사용했다. (양수 넣는 힙과 음수 넣는 힙) 입력받은 숫자들을 2개의 힙중 하나의 힙에 구분하여 넣는다. 두개의 힙중 하나라도 비어지면 반복문 종료한다. 짝이 아닐 경우 둘중 절대값이 작은 수를 res에 넣는다. (res는 짝이 없는 수들의 리스트) / 반복 반복문이 종료되면 힙에 남는 값들을 전부 res에 넣어준다. res에 들어간 값들의 합을 출력 ✅ 정답 코드 from heapq import heappop, heappush import sys.. 2023. 5. 10. [자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue) 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 사용 용도 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 특징 힙(heap)을 이용한 구현 방법 루트 노드엔 우선순위가 높은 값이 들어간다. 힙에서는 항상 루트 노드를 제거한다. 힙은 완전 이진 트리 형태로 구성되어있다. import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) heap = [] for i in range(n, 0, -1): heappush(heap, i) print('-' * 15, 'heappop', '-' * 15) for i in ra.. 2023. 5. 10. [python 백준 2075] N번째 큰수 📜 접근 방법 처음에는 heap에 내림차순으로 넣고 n만큼 빼면 n번째 큰수가 나오는 것을 생각하여 코드를 짰다. 하지만 메모리 오류 발생했다. heap안에 원소의 갯수를 제한시켜서 갯수가 n개 이상이면 현재 넣어야할 원소와 heap안에 있는 제일 작은 수를 비교한다. 현재 넣을 원소가 크다면 heap[0](가장 작은 수)에 있는 수를 pop하고 집어넣는다. 아닐경우 넘어간다. ❌ 실패 코드 메모리 오류 from heapq import heappush, heappop import sys input = sys.stdin.readline n = int(input()) heap = [] for i in range(n): tmp = list(map(int, input().split())) for num in t.. 2023. 5. 2. 이전 1 2 다음
