분류 전체보기

문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 코드 My answer import sys import heapq input=sys.stdin.readline n=int(input()) heap = [] for i in range(n): tmp=int(input()) if(tmp!=0): heapq.heappush(heap, tmp) else: if(heap==[]): print(0) else: result=heapq.heappop(heap) print(result) Another a..

문제 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 코드 My answer import sys input=sys.stdin.readline an,bn=map(int,input().split()) a=set(map(int,input().split())) b=set(map(int,input().split())) k=a&b print(an+bn-len(k)*2) Another answer input() print(len(set(input().split())^set(input().split()))) 풀이 나는..

문제 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 코드 My answer import sys input=sys.stdin.readline t=int(input()) for i in range(t): n=int(input()) cloth=dict() tmp=1 for j in range(n): a,b=input().split() if(b in cloth): cloth[b]+=1 else: cloth[b]=1 for ..

문제 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 코드 My answer import math import sys input = sys.stdin.readline n = int(input()) sell = dict() for i in range(n): book = input().rstrip() if (book in sell): sell[book] += 1 else: sell[book] = 1 sell = sorted(sell.items(), key=lambda x: (-x[1], x[0])) pri..

오늘은 heap에 대해서 알아보겠다. 우선 heap을 한단어로 설명하자면 규칙을 가진 이진트리이다. 이진트리가 무엇이냐면 각각의 노드가 최대 2개의 자식노드를 가진 트리를 말한다. 자식노드는 왼쪽 자식과 오른쪽 자식노드로 나뉜다. 다음으로 규칙으로는 최소힙과 최대힙이 있는데, 최소힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙을 말하고 최대힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙을 말한다. 위 그림처럼 두개의 자식노드만 가지면서 왼쪽 자식은 부모노드의 index*2 위치에 넣고, 오른쪽 자식은 부모노드의 index*2+1위치에 넣는다. 우선 힙은 첫번째 인덱스를 0으로 하면 계산이 복잡해져서 1로 두고 10을 인덱스 1위치에 넣는다. 다음으로 15는 1*2위치인 인덱스 2에..

문제 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 코드 My answer import sys import heapq input=sys.stdin.readline n=int(input()) heap = [] for i in range(n): tmp=int(input()) if(tmp!=0): heapq.heappush(heap, (-tmp, tmp)) else: if(heap==[]): print(0) else: result=heapq.heappop(heap) print(result[1])..