Dev.baelanche

풀이 1. 입력한 소수들을 배열에 저장하고 우선순위큐(최소힙)에 담는다. 2. 우선순위큐의 top을 제거하고 top과 1번에서 저장한 배열의 각 인덱스를 곱하여 큐에 담는다. 3. 2번을 반복한다. 위 풀이대로 진행하면 중복된 수들도 큐에 담기게 되는데, 이 부분만 예외처리 하면 시간초과 없이 문제를 풀 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); PriorityQueue pq = new PriorityQueue(); int k = sc.nextInt(); int n = sc.nextInt(); int a[] = new int[k]; for(int i=0; i

문제 설명대로 최대힙을 만들고 n번째까지 빼면서 출력했더니 시간초과가 났다. 우선순위큐가 insert, delete 할때 언제나 정렬된다는 성질을 기억해두면 문제에 접근할 수 있다. 1. 최소힙을 만든다. 2. i번째 행을 모두 집어넣는다. 3. i+1번째 행을 모두 집어넣고 크기가 n이 될때까지 제거한다. 4. n-1 행까지 2, 3번을 반복한다. 최소힙을 구현했으므로 4번까지 진행하면서 작은 수는 모두 제거된다. 남은 수의 개수는 n개 이고 오름차순 정렬이므로 top을 출력해주면 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); ..

1. 최소힙에 카드 묶음을 담는다. 2. 카드 2개를 골라서 비교한다. 3. 2번에서 비교완료한 카드 묶음을 다시 카드 묶음에 담는다. 4. 2, 3번을 반복하는데 힙의 사이즈가 0이면 비교완료한 카드 묶음이 있어도 담지 않아야 한다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); MinHeap h = new MinHeap(100001); int n = sc.nextInt(); for(int i=0; i1; i/=2) { if(heap[i/2] > heap[i]) swap(i/2, i); else break; } } public int delete() { if(size == 0..

절댓값 기준으로 최소힙으로 정렬한다. 단 -1, 1 처럼 절댓값이 같은 경우에는 음수부터 출력해야 한다. 최소힙이 구현되어있는 우선순위 큐를 사용하였고, 정렬 기준을 따로 만들어주었다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); PriorityQueue pq = new PriorityQueue(new Comparator() { @Override public int compare(Integer a1, Integer a2) { Integer n = Math.abs(a1); Integer m = Math.abs(a2); if(n ..

1부터 n-1 까지 최대힙으로 넣어준다. 마지막으로 배열의 n 자리에 1을 넣어주면 스왑이 가장 많은 힙 구조가 완성된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n+1]; for(int i=1; i1; j/=2) a[j] = a[j/2]; a[1] = i+1; } a[n] = 1; for(int i=1; i

최소 힙을 문제에 맞춰 구현했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); MinHeap h = new MinHeap(100001); int n = sc.nextInt(); for(int i=0; i1; i/=2) { if(heap[i/2] > heap[i]) swap(i/2, i); else break; } } public int delete() { if(size == 0) return 0; int root = heap[1]; heap[1] = heap[size]; size--; for(int i=1; i*2

최대힙을 구현하여 문제에 맞춰 동작하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); MaxHeap h = new MaxHeap(100001); int n = sc.nextInt(); for(int i=0; i1; i/=2) { if(heap[i/2] heap..