문제http://boj.ma/34817요약인접한 요소가 K이하일 때만 swap해서, 오름차순 정렬이 가능한 배열인지 확인하자.N ≤ 200,000풀이 과정아이디어정렬을 위해 순서를 뒤집어야 하는 쌍 중, 두 값의 차이가 K를 초과하지 않으면 정렬이 가능함을 알 수 있다.아래는 문제 조건에서 정렬이 가능한 예시이다.K = 0, A = [ 0, 9, 9999 ]K = 1, A = [ 1, 0, 9999 ]임의의 위치 i에서 오른쪽에 있는 값 중 가장 작은 값 A[j]가 A[i]의 차가 K를 초과한다면, 그 배열은 정렬이 불가능하다.인접한 두 요소만 뒤집어 정렬해야 하지만, N ≤ 2e5 이므로, 매 번 오른쪽의 값 중 가장 작은 값을 구할 수 없으므로, 미리 구하자.int[] suffixMin = new i..

문제http://boj.ma/30014요약원의 모든 요소에 대해, 인접한 쌍의 곱들의 합이 최대가 되도록 요소를 재배치하자.주어진 입력에 대한 최댓값 X는 int로 표현 가능하다.풀이 과정아이디어원의 모든 요소에 대해, 인접한 쌍의 곱들의 합이 최대가 되도록 하기 위해서는 큰 값들이 인접하도록 배치하면 된다.이를 위해서 우선 정렬 후, 큰 값부터 덱(Deque)의 좌우에 번갈아 넣어주자.// SolveArrays.sort(P);Deque deque = new ArrayDeque();for (int i = N - 1; i >= 0; --i) { if (i % 2 == 0) deque.addLast(P[i]); else deque.push(P[i]);}덱에서 요소를 하나씩..

문제http://boj.ma/2141요약일직선 상에 A[i]명이 X[i]에 위치할 때, 인원 수를 고려한 중앙값을 구하자.N ≤ 100,000, 시간 제한 ≤ 2s풀이 과정아이디어N이 1e5이므로, 완전 탐색으로 모든 위치 또는 마을로부터의 거리를 구한다면 시간 초과가 발생한다.우선 어떤 풀이를 사용하든, 마을의 위치가 오름차순으로 정렬되어 있지 않으니 정렬을 해주자.Arrays.sort(villages, (a, b) -> { return Integer.compare(a[0], b[0]);});A[i]명이 X[i]에 위치할 때, 인원 수를 고려한 중앙값은, X에 대한 가중 중앙값을 구하는 것으로 풀이할 수 있다.전체 인원(total)의 과반수가 되는 사람이 위치한 마을을 출력하면 된다.for (in..

문제http://boj.ma/29891 29891번: 체크포인트 달리기 boj.ma 풀이문제 요약주어진 N개의 체크포인트 중 한 번에 최대 K개씩 체크할 수 있을 때, 모두 왕복하기 위한 최소 이동 비용을 구하자.아이디어주어진 모든 체크포인트를 들러야하므로, 절댓값이 큰 체크포인트부터 K개의 체크포인트를 체크하며 왕복해, 전체 이동 비용을 낮춰야 한다.양수/음수는 따로 계산해야한다는 점에 유의하자. // Solve Arrays.sort(A); long sum = 0; for (int i = 0; i = 0 && A[i] > 0; i -= K) { sum += A[i]; } // Output System.out.println(sum * 2);풀이 시간10분소스코드https://github...

문제http://boj.ma/9440 9440번: 숫자 더하기 boj.ma 풀이문제 요약N개의 수를 사용해 합이 최소인 두 수를 만들자.아이디어두 수의 합이 최소가 되기 위해서는, 주어진 수를 오름차순으로 정렬 후 번갈아 사용해 두 수를 만들면 된다.두 수의 큰 자릿수에 작은 수를 부여해야 두 수의 합이 작아지기 때문이다.N개의 수의 빈도를 구하고,0이 아닌 가장 작은 수를 두 수에 부여한 후,남은 수들을 번갈아가며 부여하면 된다.public class Main { private static int solve(int[] A, int N) { ... int[] nums = new int[2]; for (int idx = 0; idx 0) { ..

문제http://boj.ma/2643 2643번: 색종이 올려 놓기 boj.ma 풀이문제 요약N개의 직사각형 종이를 자신보다 크거나 같은 종이 위에만 쌓아 가장 높게 쌓을 때의 높이를 구하자.아이디어종이는 서로의 변에 대해 평행하게만 놓을 수 있으므로 (작은 변의 길이, 큰 변의 길이)를 기준으로 입력받고, 오름차순으로 정렬하자.public class Main { private static class Point { int x, y; public Point(int x, int y) { this.x = Math.min(x, y); this.y = Math.max(x, y); } } A.sort((a, b) -> { if (a.x == b.x) { return Integer.compar..

문제http://boj.ma/2024 2024번: 선분 덮기 boj.ma 풀이문제 요약구간 [0, M]을 덮기 위한 선분의 최소 갯수를 구하자아이디어구간 내 여러 선분들이 끊기지 않고, 구간을 전부 덮을 수 있는지 확인해야한다.구간에 포함되거나 걸치는 선분의 시작점과 끝점을 오름차순으로 정렬 후, 중첩된 선분을 만들어가면 된다.만약 구간이 끝나지 않았는데, 현재 선분에서 더 이상 확장할 수 없다면 구간을 덮을 수 없는 경우다. while (cur 풀이 시간20분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/03024.java problem-solving/baekjoon-online-judge..

문제http://boj.ma/11497 11497번: 통나무 건너뛰기 boj.ma 풀이문제 요약N개의 통나무를 원형으로 놓았을 때 인접한 통나무의 최대 높이차가 최소가 되도록 배치하자.아이디어통나무를 단순히 정렬하면 1, N 번 통나무의 높이차로 인해, 좋은 배치가 될 수 없다.우선 오름차순으로 정렬 후, 작은 요소부터 0번 인덱스의 양 옆에 번갈아가며 배치하면 된다. 번갈아 가는 순서는 동일하게 반복만 된다면 왼쪽/오른쪽 중 아무 방향으로 먼저 놓아도 된다. // Solve Arrays.sort(A); int[] B = new int[N]; for (int i = 0; i 풀이 시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/mai..

문제http://boj.ma/1374 1374번: 강의실 boj.ma 풀이문제 요약강의 N개의 시작, 종료 시간이 주어졌을 때 모든 강의를 진행하기 위해 필요한 최소 강의실을 수를 구하자.아이디어가장 일찍 끝나는 강의 다음으로 또 다른 강의를 시작할 수 있는 지에 따라 필요한 강의실의 수가 결정된다.우선 강의 정보를 (시작, 종료)를 기준으로 오름차순 정렬 해주자.최소힙에 강의 종료 시간을 차례대로 넣어주며, 가장 일찍 끝나는 강의 시간과, 다음 강의의 시작 시간을 비교하면 된다. 최소힙의 각 노드수는 만약 연강이 가능하다면 루트 노드가 갱신 될 것이며, 결국 최소힙의 노드 수는 강의실 수가 된다. // Solve Arrays.sort(lectures, (a, b) -> { ..

문제http://boj.ma/28359 28359번: 수열의 가치 boj.ma 풀이문제 요약주어진 수열이 증가하지 않는 부분 수열(P), 감소하지 않는 부분 수열(C)가 되도록 재배열하여 주어진 규칙대로 수열의 가치가 최댓값을 가지도록 하자.아이디어예제의 경우 P = {1, 2, 2}, Q = {3, 2, 2} 로 구성되며, {2, 2}가 중복되어 최대 가치 12를 가진다.수열의 가치에 중복 계산하는 수를 제외한다면, 수열을 재배열 할 때 P 또는 Q는 1개의 요소로도 충분하므로 정렬을 수행할 수 있다.P 또는 Q는 부분 수열이므로, 중복 계산되는 수를 포함하는 것으로 충분하다.중복 계산되는 수는 빈도와 값의 곱이 큰 수로 결정해주자. // Solve Arrays.sort(A);..