기록방

👉 문제링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 🔸 문제 분석 🔸 카드 묶음들을 합칠때 최소 비교 횟수를 출력한다. 🔸 문제 풀이 🔸 작은 묶음부터 합쳐야 최소값이 나오는걸 문제에서 확인할 수 있으므로, 그리디 알고리즘으로 접근해 우선순위 큐를 이용하여 풀이한다. 두 최소값 원소를 뽑아 그 합을 정답에 누적하고, 다시 그 합을 우선순위 큐에 넣는다. 우선순위 큐의 원소가 1개가 남을 때 까지 반복한다. 합으로 만들어진 새 묶음이 기존 묶음보다 클 수 있음에 유의한다. 🔸 코드 🔸 i..

👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 새로운 데이터가 입력될 때 마다 내림차순 정렬했을 때, k 번째 수를 출력한다. 배열의 정렬은 시간 복잡도가 커지므로 java 우선순위 큐의 최대 힙을 사용해 정렬한다. 🔸 코드 🔸 import java.util.PriorityQueue; class Solution { public int[] solution(int k, int[] score) { int[] answer = new int[score.length]; PriorityQueue que = new PriorityQueue..

👉 문제링크 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 🔸 문제 분석 🔸 int 범위의 값을 넣는 'I' 연산과 최대값 혹은 최소값을 빼는 'D'연산이 k번 수행된다. 최종 연산 후 결과를 출력한다. k의 최대값이 1,000,000 이므로 값을 저장할 자료구조를 힙 형태로 구현해야 한다. 힙정렬이 적용된, 우선순위 큐(Priority Queue) 혹은 TreeMap을 사용한다. 🔸 Priority Queue 🔸 import java.io.BufferedReader; import java.io.IOEx..

👉 문제링크 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 🔸 문제 분석 🔸 n의 범위가 100,000이므로 O(nlogn) 시간 복잡도 알고리즘으로 풀 수 있다. 데이터가 삽입 될 때마다 절댓값으로 정렬되는 우선순위 큐를 사용한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; public class..