기록방

👉 문제링크 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..

👉 문제링크 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 🔸 문제 분석 🔸 일정 범위 안에서 최소값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용해야 한다. 윈도우의 크기는 최소값을 구하는 범위가 i-L+1 ~ i 이므로 L로 생각한다. 일반적으로 정렬은 O(nlogn)인데 N,L 의 범위가 5,000,000까지 이므로 정렬은 사용하지 못한다. O(n)의 시간 복잡도로 해결해야되므로 윈도우를 덱(deque)로 구현하여 정렬 효과를 낸다. 덱은 (인덱스, 숫자) 형태의 노드..

👉 문제링크 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 🔸 문제 분석 🔸 배열의 첫째자리가 최대값이 되도록 다른 인덱스에서 값을 가져오는데 드는 최소 횟수를 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { Buff..