Dev.baelanche

문제 설명대로 최대힙을 만들고 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..

배열에 대해서 방문한 적이 없고 땅이라면 인접한 땅에 대해서 DFS 를 한다. DFS 한 컴포넌트의 개수를 세어주면 된다. public class Main { static int w; static int h; static int a[][]; static boolean visited[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { w = sc.nextInt(); h = sc.nextInt(); if(w == 0 && h == 0) break; a = new int[h][w]; visited = new boolean[h][w]; for(int i=0; i

수의 개수가 10,000,000 이라 배열에 모두 담게되면 메모리 초과로 풀 수 없다. 정렬할 수가 10000 이하 라는것을 이용하여 수가 입력된 개수를 세어 정렬하는 카운팅 정렬(계수 정렬)으로 풀 수 있다. 풀이 1 public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); int a[..