흙금이네 블로그

아이디어 투 포인터로 좋은 수의 개수를 센다. 풀이 리스트 numbers에 입력 받은 숫자들을 정렬하여 저장한다. for문에서 현재 수를 numbers에서 제외한 후 search 함수를 호출하여 반환값을 결과값 res에 더한다. search 함수가 종료되면 제외했던 현재 수를 다시 numbers에 추가하는 식으로 for문을 반복한 후 결과값을 출력한다. search 함수는 numbers의 두 수를 더해 찾고자 하는 수를 찾으면 1을 반환한다. 시작 인덱스 s와 끝 인덱스 e에서 s가 e보다 작은 동안 반복하며, 현재 수를 찾지 못하면 0을 반환한다. def search(num): s = 0 e = N-2 while s temp:..

아이디어 크루스칼 알고리즘을 사용한 최소 신장 트리로 집을 모두 연결한 최소 비용을 전체 비용에서 뺀다. 풀이 최소 신장 트리를 구현하기 위해 집합을 찾는 find 함수와 두 집합을 합치는 union 함수를 정의한다. 집의 수는 M, 길의 수는 N으로 입력 받고, while문은 집의 수 M이 유효한 동안 반복된다. 길에 대한 정보를 거리 순으로 정렬한 road 리스트를 만들고 유니온 파인드로 두 집이 연결되지 않았을 때 연결한다. road 리스트를 만들 때 전체 비용 합을 res에 저장해두고, 두 집이 연결될 때마다 res에서 해당 비용을 뺀다. 연결된 횟수(간선 개수) cnt가 M-1이 되면 for문을 종료하고 결과값 res를 출력한다. import sys input = sys.stdin.readlin..

아이디어 최소힙과 최대힙의 두 가지 우선순위 큐를 사용하여 중앙값을 찾는다. 풀이 최대힙 left와 최소힙 right를 빈 리스트로 생성하고, 처음 입력 받는 값을 중앙값 mid로 저장한다. 이후 중앙값과 비교해 작거나 같은 값은 최대힙 left에, 큰 값은 최소힙 right에 push한다. 두 힙의 크기가 2 이상 차이나는 경우 현재 중앙값은 크기가 작은 힙에 push하고, 크기가 큰 힙에서 루트 노드를 pop하여 중앙값을 새롭게 바꾸고 힙의 균형을 맞춘다. 홀수 번째 입력 때마다 중앙값을 결과값에 숫자를 문자열로 추가하고, 조건에 따라 개행 문자를 추가한다. import sys, heapq input = sys.stdin.readline T = int(input()) for t in range(T):..