PriorityQueue

    [Java] 백준 1933 (스카이라인) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1933 (스카이라인) Gold 2

    Problem : https://www.acmicpc.net/problem/1933 1933번: 스카이라인 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오 www.acmicpc.net Approach 우선순위 큐(PriorityQueue)와 TreeMap 자료구조를 활용하는 문제이다. 문제에서 원하는 것은 높이가 변하는 부분의 x좌표와 그 때의 최대높이이다. 이를 위해 우선순위 큐와 TreeMap을 사용한다. 우선순위 큐는 x좌표 기준 오름차순(같을 경우, 높이 기준 내림차순)으로, 트리맵은 높이 기준 내림차순의 정렬 기준을 규정한다..

    [Java] 백준 21773 (가희와 프로세스 1) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 21773 (가희와 프로세스 1) Gold 5

    Problem : https://www.acmicpc.net/problem/21773 21773번: 가희와 프로세스 1 1초일 때 부터 4초일 때 상황을 그림으로 나타내면 아래와 같습니다. 아래 그림에서 주황색은 특정 시점에 스케쥴러가 선택한 프로세스를 의미합니다. www.acmicpc.net Approach 우선순위 큐(PriorityQueue) 를 이용한 문제이다. 문제의 로직은 다음과 같다. 레디 큐에서 가장 우선순위가 높은 프로세스를 꺼내 1초동안 실행시킨다. 꺼낸 프로세스를 제외한 레디 큐에 있는 모든 프로세스의 우선순위는 1증가한다. 위 로직을 구현하려면, 먼저 우선순위 큐의 정렬 기준을 확립해야 한다. 프로세스의 우선순위 기준 내림차순이 필요할 것이다. 이제 우선순위큐에서 프로세스를 하나 뽑..

    [Java] 백준 2109 (순회강연) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2109 (순회강연) Gold 4

    Problem : https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net Approach 우선순위 큐를 사용한 그리디(Greedy) 알고리즘 문제이다. 먼저 pay 기준 내림차순으로 정렬된 우선순위 큐가 필요하다. pay가 같을 경우에는 day가 더 작은 것이 우선이다. 그리고 주어진 입력 d의 최대 크기만큼의 cost 배열을 선언한다. cost[i] 는 i일에 얼마짜리 강의를 하는지를 저장한다. cost 배열의 총..

    [Java] 백준 1202 (보석 도둑) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1202 (보석 도둑) Gold 2

    Problem : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net Approach 우선순위 큐를 활용한 Greedy 문제이다. 접근법을 떠올렸다면 쉽게 구현할 수 있다. (PriorityQueue 이용하여) 먼저 보석과 가방을 각각 무게 기준 오름차순으로 정렬한다. 각 가방에 대하여 가방의 무게보다 작은 보석들을 pq에 넣는다. (pq는 보석의 가치 기준 내림차순의 우선순위를 가진다...

    [Java] 백준 1766 (문제집) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1766 (문제집) Gold 2

    Problem : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net Approach 위상정렬 + PriorityQueue 를 활용한 문제이다. 위상정렬을 알고 있다면 꽤 쉬운 문제이다. 문제를 풀이하는데 있어 순서가 존재하므로 위상정렬을 떠올릴 수 있었다. 또한, 지금 풀 수 있는 문제가 여러개일 때, 번호가 작은 문제부터 풀어야 하므로 우선순위 큐를 생각할 수 있겠다. 입력을 모두 받을 때까지 inDegree 배열..

    [Java] 백준 1261 (알고스팟) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1261 (알고스팟) Gold 4

    Problem : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net Approach 이 문제의 기본 접근법은 갈 수 있는 곳 중 벽이 아닌 곳이 있으면 우선 그 쪽으로 가고, 갈 수 있는 곳이 벽인 곳밖에 없다면 벽을 뚫는다.이다. 이를 구현하는 데에는 여러 방법이 있겠지만, 나는 Deque+BFS, PriorityQueue+BFS 두 가지 방법으로 풀이를 해봤다. 두 방법 모두 풀이가 가능하다. 주의할 점은, 큐에 동일한 ..

    [Java] 프로그래머스 (야근 지수) Level 3
    Algorithm/Programmers

    [Java] 프로그래머스 (야근 지수) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr Approach 우선순위 큐(PriorityQueue)를 이용하여 문제를 풀었다. 자바의 PriorityQueue 는 Heap으로 내부동작이 이루어져서 시간복잡도가 O(NlogN)이다. N이 최대 1,000,000 이라 시간초과가 나지 않을까도 싶었지만 다행이도 시간초과는 나지 않았다. 우선순위 큐를 큰 숫자가 우선이 되게끔 Co..

    [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..

티스토리툴바