heap

    [java] 프로그래머스 (이중우선순위큐) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (이중우선순위큐) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr Approach 힙(Heap)이나 우선순위큐(PriorityQueue)를 사용하여 풀이가 가능한 문제이다. 나는 처음 문제를 보고 PriorityQueue와 Deque을 생각했다. 그러나 하나의 PriorityQueue에서는 최솟값과 최댓값을 한 번에 처리할 수 없었고, Deque는 정렬된 상태를 유지하는 방법을 찾지 못했다. 최소한의 자료구조를 가지고 문제를 풀고 싶었다. 내가 필요한 자료구조는 정렬된 상태를 유지하는 것과 최댓값과 최솟값을 뽑을 수 있는 자료구조였다. 그래서 생각한 것이 TreeSet이다. 간단하게 설..

    [java] 백준 1655 (가운데를 말해요) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 1655 (가운데를 말해요) Gold 2

    Problem : https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net Approach 최대 힙과 최소 힙 두개를 사용하여 문제를 풀 수 있다. 최대 힙은 최댓값이 우선으로 빠져나오는 큐이고, 최소 힙은 최솟값이 우선으로 빠져나오는 큐라고 할 때, 최대 힙과 최소 힙에 하나씩 숫자를 넣는다고 가정햇을 때, 최대 힙의 최댓값이 최소 힙의 최솟값보다 항상 작음을 유지한다면, 최대 힙의 최댓값이 항상 중간값을 가지게 된다. 그러기 위해선 ..

    [java] 백준 11286 (절댓값 힙) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 11286 (절댓값 힙) Silver 1

    Problem : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Approach PriorityQueue를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. 절댓값이 가장 작은 값을 출력하려면 PriorityQue..

    [java] 백준 11279 (최대 힙) Silver 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 11279 (최대 힙) Silver 2

    Problem : https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net Approach PriorityQueue를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. 하지만 가장 큰 값이 나와야 하므로 별도의 설정이 필요하다..

    [java] 백준 1927 (최소 힙) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1927 (최소 힙) Silver 1

    Problem : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Approach 우선순위 큐(PriorityQueue)를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. Code import java.io.*; i..

티스토리툴바