백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.
출력
한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.
🍀 풀이
두 개의 우선순위 큐를 활용하여 문제를 풀었다.
하나는 가장 큰 값을 가져오는 우선순위 큐로, 여기에는 백준이가 지금까지 부른 숫자 중 절반에 해당하는 작은 값들을 저장한다. (`small_pq`)
지금까지 부른 숫자가 홀수개인 경우 이곳에 숫자 하나를 더 넣는다.
다른 하나는 가장 작은 값을 가져오는 우선순위 큐로, 여기에는 백준이가 지금까지 부른 숫자 중 절반에 해당하는 큰 값들을 저장한다. (`big_pq`)
항상 `small_pq`의 사이즈와`big_pq`사이즈가 같거나,`small_pq`의 사이즈가`big_pq`사이즈보다 1 커야한다.
입력을 받은 후 `small_pq`의 가장 큰 값이 중간값이 되도록 만들 것이다.
7
1
5
2
10
-99
1
위와 같은 예시가 주어졌다고 했을 때, 먼저 첫번째 입력은 `small_pq`에 넣고 이를 출력한다.
그 다음 입력은 `small_pq`의 가장 큰값과 비교한다. 예시에서는 1보다 큰 5가 입력으로 주어졌다.
`small_pq`보다 입력값이 큰 경우는 `big_pq`에 저장한다.
`small_pq`와 `big_pq`의 사이즈가 같으므로 중간에 있는 수 중 더 작은 `small_pq`의 가장 큰 값을 출력한다.
그 다음 입력인 2는 1보다 크므로 `big_pq`에 저장한다.
`small_pq`의 사이즈보다 `big_pq`의 사이즈가 크다.중간값을 항상`small_pq`의 제일 큰 값으로 가져오기 위해서`small_pq`보다 `big_pq`의 사이즈가 큰 경우,`big_pq`의 제일 작은 값을 빼서 `small_pq`에 넣는다.
`small_pq`의 사이즈가 `big_pq`의 사이즈보다 1 크므로 중간값인 `small_pq`의 가장 큰 값을 출력한다.
그 다음 입력인 10은 2보다 크므로`big_pq`에 저장한다.
`small_pq`와 `big_pq`의 사이즈가 같으므로 중간에 있는 수 중 더 작은 `small_pq`의 가장 큰 값을 출력한다.
그 다음 입력인 -99은 2보다 작으므로`small_pq`에 저장한다.
`small_pq`의 사이즈가 `big_pq`의 사이즈보다 1 크므로 중간값인 `small_pq`의 가장 큰 값을 출력한다.
그 다음 입력인 1은 2보다 작으므로`small_pq`에 저장한다.
`big_pq`의 사이즈를 +1한 것보다 `small_pq`의 사이즈가 크다.중간값을 항상`small_pq`의 제일 큰 값으로 가져오기 위해서`big_pq`의 사이즈+1 보다 `small_pq`의 사이즈가 큰 경우,`small_pq`의 제일 큰 값을 빼서 `big_pq`에 넣는다.
`small_pq`의 사이즈가 `big_pq`의 사이즈보다 1 크므로 중간값인 `small_pq`의 가장 큰 값을 출력한다.
1. 우선순위 큐를 정의한다. 1. `small_pq`: 가장 큰 값을 가져오는 우선순위 큐 2. `big_pq`: 가장 작은 값을 가져오는 우선순위 큐 2. 제일 첫 입력을 `small_pq`에 넣고, 이를 출력한다. 3. `N-1`만큼 반복하며 입력을 받는다. 1. 입력을 받아 `target`에 저장한다. 2. `small_pq`의 제일 큰 값보다 `target`이 크다면, `big_pq`에 `target`을 넣는다. 1. `target`을 넣은 후 `big_pq`의 사이즈가 `small_pq`사이즈 보다 크다면, `big_pq`의 제일 작은 원소를 빼서 `small_pq`에 넣는다. 3. `small_pq`의 제일 큰 값보다 `target`이 작거나 같다면, `small_pq`에 `target`을 넣는다. 1. `target`을 넣은 후 `small_pq`의 사이즈가 `big_pq`사이즈+1한 값보다 크다면, `small_pq`의 제일 큰 원소를 빼서 `big_pq`에 넣는다. 4. `target`을 우선순위 큐에 넣었다면, `small_pq`의 제일 큰 원소를 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine()) - 1;
PriorityQueue<Integer> small_pq = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> big_pq = new PriorityQueue<>();
small_pq.offer(Integer.parseInt(br.readLine()));
sb.append(small_pq.peek()).append("\n");
while (0 < N--) {
int target = Integer.parseInt(br.readLine());
if (small_pq.peek() < target) {
big_pq.offer(target);
if (small_pq.size() < big_pq.size()) {
small_pq.offer(big_pq.poll());
}
} else {
small_pq.offer(target);
if (big_pq.size() + 1 < small_pq.size()) {
big_pq.offer(small_pq.poll());
}
}
sb.append(small_pq.peek()).append("\n");
}
System.out.print(sb);
}
}
💫 리뷰
우선순위 큐를 잘 활용하면 됐던 문제! 옛날에 이런 비슷한 문제를 풀었던 것 같아서 풀이법이 바로 생각났다.
위와 같은 입력이 들어왔다고 한다면, 아이템에게 번호를 부여하여 아래 그림과 같이 변경하였다.
아이템은 최대 5개이므로 char형 배열에 저장할 수 있다!
각 아이템 번호를 자릿수처럼 생각하며left shift 연산(`1<<n`)을 활용했다.
e.g. 아이템 2번 1을 왼쪽으로 2만큼 비트 이동한다. 100(bit) = 4(십진수)
경재가 여러 아이템을 발견한 경우 OR 비트연산(`|`)을 활용했다.
e.g. 경재가 0번 아이템만 가지고 있다가, 2번 아이템을 발견했을 때
경재가 최소 시간으로 물건을 찾고 외출해야하므로 너비 우선 탐색 BFS을 이용했다.
이때 방문처리는 현재 경재가 찾은 물건의 종류에 따라서 다르게 처리해야 한다고 생각했다.
아래 그림처럼 1번 아이템을 얻은 후 경재가 다시 왔던 길을 돌아가야하는 데, 방문처리를 2차원 배열로 한다면 돌아가지 못한다.
녹색이 경재의 현위치, 빨강색은 방문했던 곳
3차원 배열을 만들어 OR 비트연산한 결과에 따라서 다르게 방문처리할 수 있도록 구현했다.
OR 비트연산(`|`)을 통해 경재는 아이템이 하나도 없는 '0'부터 모든 아이템을 다 가진 '(1<<아이템 수) -1' 까지의 비트를 활용했다.
마지막으로 'E'에 도착했을 때, 경재가 모든 아이템을 다 찾았는지 체크하는 것은 비트 수를 확인했다.
1. 집의 구조를 입력받는다. 1. 해당 칸에 아이템이 있는 경우 'X', X대신 아이템 번호(`itemCount`)로 저장하고 `itemCount`를 증가시킨다. 2. 해당 칸이 출발 점인 경우, 변수로 위치를 저장하고 해당칸은 비어있는 곳 '.'으로 변경한다. 2. `findItem()`함수를 호출하여 외출하기까지 최소 시간을 구한다. 3. 경재의 움직임을 저장할 큐 `queue`를 선언한다. queue의 원소에는 {현재 위치의 행, 현재 위치의 열, 소요시간, 비트화한 획득한아이템}을 저장한다. 4. 방문처리할 3차원 boolean 배열 `visited`를 선언한다. [행][열][비트화한 획득한아이템] 5. 경재의 시작 위치에 맞게 `queue`에 원소를 넣고, `visited`방문처리를 한다. 경재는 아직 가진 아이템이 없으므로 비트화한 획득한아이템은 0이다. 6. `queue`가 빌 때까지 반복한다. 1. `queue`에서 원소를 빼 `node`에 저장한다. 2. 상하좌우 사방탐색을 하며 경재를 이동시킨다. 1. 이동한 위치가 벽'#'이거나, 방문한적이 있는 경우 다음 반복문으로 넘어간다. 2. 이동한 위치가 비어있는 곳'.'이라면, 이동한 위치에 방문 처리를 하고 `queue`에 원소를 넣는다. 3. 이동한 위치가 나가는 문'E'이고 경재가 모든 아이템을 다 챙겼다면 소요시간+1을 반환하며 함수를 종료한다. 4. 이동한 위치가 아이템이 있는 경우('0'~'4' 중 하나), OR 비트연산을 통해 아이템을 획득하고 이동한 위치에 방문 처리를 하고 `queue`에 원소를 넣는다. 7. `findItem()`함수가 종료됐다면, 반환값을 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N, M;
static int itemCount, s_i, s_j;
static char[][] map;
public static void main(String[] args) throws Exception {
init();
System.out.println(findItem());
}
static void init() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
N = Integer.parseInt(input.substring(0, input.indexOf(' ')));
M = Integer.parseInt(input.substring(input.indexOf(' ') + 1));
itemCount = 0;
map = new char[M][];
for (int m = 0; m < M; m++) {
map[m] = br.readLine().toCharArray();
for (int n = 0; n < N; n++) {
if (map[m][n] == 'X') {
map[m][n] = (char) (itemCount++ + '0');
} else if (map[m][n] == 'S') {
s_i = m;
s_j = n;
map[m][n] = '.';
}
}
}
}
static int findItem() {
final int[] di = new int[]{-1, 0, 1, 0};
final int[] dj = new int[]{0, 1, 0, -1};
Queue<int[]> queue = new LinkedList<>();
boolean[][][] visited = new boolean[M][N][1 << itemCount];
queue.offer(new int[]{s_i, s_j, 0, 0});
visited[s_i][s_j][0] = true;
while (!queue.isEmpty()) {
int[] node = queue.poll();
for (int z = 0; z < 4; z++) {
int ni = node[0] + di[z];
int nj = node[1] + dj[z];
if (map[ni][nj] == '#' || visited[ni][nj][node[3]]) continue;
if (map[ni][nj] == '.') {
visited[ni][nj][node[3]] = true;
queue.offer(new int[]{ni, nj, node[2] + 1, node[3]});
} else if (map[ni][nj] == 'E') {
if (itemCount == Integer.bitCount(node[3])) return node[2] + 1;
} else {
visited[ni][nj][node[3] | 1 << (map[ni][nj] - '0')] = true;
queue.offer(new int[]{ni, nj, node[2] + 1, node[3] | 1 << (map[ni][nj] - '0')});
}
}
}
return 0;
}
}
💫 리뷰
다른 방식으로 접근하고 있다가 비슷한 문제를 풀었던 기억이 나면서 해결할 수 있었던 문제!
김지민은 학생들에게 K개의 글자를 가르칠 수 있고, 가르치고 난 후 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다.
남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.
출력
첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.
🍀 풀이
2^26은 int형 범위 안에 있기 때문에'학생들이 배운 알파벳'을 비트화하였다.
알파벳의 순서를 자릿수처럼 생각하며left shift 연산(`1<<n`)을 활용했다.
e.g. c를 비트화 1을 왼쪽으로 2('c' - 'a')만큼 비트 이동한다. 100(bit) = 4(십진수)
학생들이 배우는 알파벳이 여러개인 경우 OR 비트연산(`|`)을 활용했다.
e.g. 학생들이 a와 c를 배운 경우 1(bit) | 100(bit) = 101(bit) = 5(십진수)
같은 방법으로 남극 언어의 단어마다 알파벳들을 비트화해서 저장했다.
비트 수를 체크하여 `K`개의 알파벳을 배웠는 지 확인했다.
`K`개의 알파벳을 배웠다면, 남극 언어의 단어들을 순차적으로 확인하며 배운 알파벳으로 읽을 수 있는 단어인지 확인했다.
이때는 AND 비트연산(`&`)을 활용했다.
배운 언어와 남극 언어의 단어를 AND 비트연산하면 공통된 부분이 추출된다.
공통된 부분이 남극 언어의 단어와 같은 경우, 배운 알파벳으로 해당 단어를 읽을 수 있다는 뜻이다.
e.g. 'antancttica' 배운 언어와 남극 언어의 단어를 AND 비트연산한 결과가 남극 언어의 단어와 일치한다. 학생들은 해당 단어를 읽을 수 있다.
e.g. `antabndtica' 배운 언어와 남극 언어의 단어를 AND 비트연산한 결과가 남극 언어의 단어와 불일치한다. 학생들은 해당 단어를 읽을 수 없다.
1. `fixedBit`: [a, n, t, i, c]은 필수로 배워야하는 알파벳이므로 미리 비트로 만들어 저장한다. 2. 남극 언어의 단어들을 순차적으로 입력받는다. 단어별로 포함된 알파벳을 모두 OR 비트연산한 후 `wordsBit`에 저장한다. 3. 부분집합을 활용하여 알파벳을 배우는 함수 `checkedAlphabet`을 호출한다. 1. `index`: 현재 배울 예정인 알파벳의 순서를 저장한다. (`a`= 0, `b`= 1, ... ) 2. `currentBit`: 학생들이 배운 알파벳들을 OR 비트연산한 결과를 저장한다. 4. 학생들이 배운 알파벳 개수가 `K`개인 경우 1. 남극 언어의 단어들을 순차적으로 확인하며 학생들이 배운 알파벳으로 만들 수 있는 단어인지 확인한다. 맞다면 `wordCount`를 1 더한다. 2. `wordCount`가 `max`보다 크다면 `max`값을 갱신한다. 3. 함수를 종료한다. 5. 모든 알파벳을 확인했다면 함수를 종료한다. 6. `currentBit`에 포함되지 않은 알파벳이라면 포함시킨 후 `checkedAlphabet`를 재귀호출한다. ([a, n, t, i, c] 때문에 조건이 붙는다) 7. 현재 알파벳을 포함시키지 않고, `checkedAlphabet`를 재귀호출한다. 8. `checkedAlphabet`가 모두 종료되면 `max`를 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int K, max, fixedBit;
static int[] wordsBit;
public static void main(String[] args) throws Exception {
init();
checkedAlphabet(0, fixedBit);
System.out.println(max);
}
static void init() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int N = Integer.parseInt(input.substring(0, input.indexOf(' ')));
K = Integer.parseInt(input.substring(input.indexOf(' ') + 1));
max = 0;
fixedBit = (1 << ('a' - 'a')) | (1 << ('n' - 'a')) | (1 << ('t' - 'a')) | (1 << ('i' - 'a')) | (1 << ('c' - 'a'));
wordsBit = new int[N];
for (int n = 0; n < N; n++) {
input = br.readLine();
int bit = fixedBit;
for (int i = 4; i < input.length() - 4; i++) {
bit |= (1 << (input.charAt(i) - 'a'));
}
wordsBit[n] = bit;
}
}
static void checkedAlphabet(int index, int currentBit) {
if (Integer.bitCount(currentBit) == K) {
int wordCount = 0;
for (int wordBit : wordsBit) {
if ((currentBit & wordBit) == wordBit) {
wordCount++;
}
}
if (max < wordCount) max = wordCount;
return;
}
if (index == 26) return;
if ((currentBit & (1 << index)) == 0) checkedAlphabet(index + 1, currentBit | (1 << index));
checkedAlphabet(index + 1, currentBit);
}
}
💫 리뷰
10개월 전에 도전했다가 실패했던 문제! 나.. 성장했다!!! ๑•̀∀•́ฅ
비트마스킹은 문제를 보고 비트마스킹으로 풀어야 겠다는 생각이 바로 안나서 어렵지만, 비트마스킹 문제라는것을 알고 풀이를 고민하는 과정은 재밌다.ㅎㅎ
강호는 모든 문제를 풀 수 있는 팀을 만들고 싶어 한다. 강호가 선택할 수 있는 팀원의 목록과 각각의 팀원들이 해결할 수 있는 문제의 번호들이 주어졌을 때 강호가 IUPC에서 최소한의 팀원으로 모든 문제를 다 풀어 우승할 수 있도록 팀을 만들어보자.
입력
첫 번째 줄에 문제의 수 N과 강호가 팀원으로 고를 수 있는 학생들의 수 M이 공백을 구분으로 차례대로 주어진다. N과 M은 1이상 10이하의 자연수이다.
두 번째 줄부터 M개의 줄에 차례대로 i(1 ≤ i ≤ M)번 학생들이 풀 수 있는 문제의 개수 Oi와 i번 학생이 풀 수 있는 문제의 번호 Pij(1 ≤ j ≤ Oi, 1 ≤ Pij≤ N)가 Oi개 주어진다.
출력
모든 문제를 풀 수 있으면서 팀원의 수가 가장 적은 팀을 구해 팀원의 수를 출력한다. 만약 모든 문제를 풀 수 있는 팀을 만들 수 없다면 -1을 출력한다.
🍀 풀이
문제 수가 최대 10개로 주어졌다. 2^10은 int형 범위 안에 있기 때문에 '현재 팀에서 풀 수 있는 문제'를 비트화하였다.
문제 번호를 자릿수처럼 활용하여 `n`번 문제를 비트화하는 경우 left shift 연산(`1<<n`)을 활용했다.
e.g. 3번 문제 1을 왼쪽으로 3만큼 비트 이동한다. 1000(bit) = 8(십진수)
한 학생이 여러 문제를 풀 수 있는 경우 OR 비트연산(`|`)을 활용했다.
e.g. 한 학생이 1, 4번 문제를 풀 수 있는 경우 10(bit) | 10000(bit) = 10010(bit) = 18(십진수)
팀을 구성할 때는 비트 수를 확인했다.
1. 영입하려는 학생이 현재 구성된 팀원들의 풀 수 없는 문제를 풀 수 있는지 확인한다.
현재 구성된 팀원들이 풀 수 있는 문제를 모두 OR 비트연산 한 결과(A)
A에 영입하려는 학생이 풀 수 있는 문제를 OR 비트연산 한 결과(B)
(1) A와 B의 비트 수가 같다면, 해당 학생이 풀 수 있는 문제는 이미 팀원들이 풀 수 있는 문제라는 의미이다.
(2) A의 비트 수보다 B의 비트 수가 크다면, 해당 학생이 풀 수 있는 문제 중 현재 구성된 팀원들의 풀 수 없는 문제가 있다는 의미이다.
2. 현재 구성된 팀원들의 모든 문제를 풀 수 있는 순간 팀원 영입은 끝난다.
현재 구성된 팀원들의 비트 수가 N개라면, 모든 문제를 풀 수 있다는 의미이다.
1. userInfos에 해당 학생이 풀 수 있는 문제 수와 문제들을 OR 비트연산한 결과를 저장한다. 2. 입력 값을 다 저장했다면, userInfos를 풀 수 있는 문제 수의 내림차순으로 정렬한다. 3. makeTeam함수에서는 비트연산과 재귀를 통해 강호의 팀을 구성한다. 1. currentBit: 현재까지 영입한 팀원들이 풀 수 있는 문제들을 모두 OR 비트연산한 결과 2. startIndex: 현시점에서 학생 배열에서 확인할 시작 인덱스값 3. memberCount: 팀원 수 4. answer보다 memberCount가 크거나 같다면 함수를 종료한다. (현재 팀은 answer보다 최소값이 나올 수 없다.) 5. 현재 구성된 팀으로 모든 문제를 풀 수 있다는 의미이므로 answer를 memberCount로 갱신하고 함수를 종료한다. 6. startIndex번째 학생부터 순차적으로 정보를 확인한다. 1. m번째 학생이 현재 팀원들이 풀 수 없는 문제를 풀 수 있다면, 영입 후 makeTeam함수를 재귀로 호출한다. 7. makeTeam함수가 모두 종료되면 answer를 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M, answer;
static int[][] userInfos;
public static void main(String[] args) throws Exception {
init();
makeTeam(0, 0, 0);
System.out.println(answer == M + 1 ? -1 : answer);
}
static void init() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
answer = M + 1;
userInfos = new int[M][2];
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine(), " ");
int count = Integer.parseInt(st.nextToken());
int bit = 0;
for (int i = 0; i < count; i++) {
bit |= (1 << Integer.parseInt(st.nextToken()));
}
userInfos[m] = new int[]{count, bit};
}
Arrays.sort(userInfos, (o1, o2) -> o2[0] - o1[0]);
}
static void makeTeam(int currentBit, int startIndex, int memberCount) {
if (answer <= memberCount) return;
if (Integer.bitCount(currentBit) == N) {
answer = memberCount;
return;
}
for (int m = startIndex; m < M; m++) {
if (Integer.bitCount(currentBit) < Integer.bitCount(currentBit | userInfos[m][1])) {
makeTeam(currentBit | userInfos[m][1], m + 1, memberCount + 1);
}
}
}
}
1. `rockIslands`에 `0`을 넣고 이후는 돌섬의 위치를 저장하고, 입력을 다 받으면 오름차순 정렬한다. 2. `start`는 출발지점인 `0`, `end`는 도착지점인 `d`로 초기화시킨 후 이분탐색을 진행한다. 1. `pt`는 학생들이 현재 위치해있는 돌섬의 인덱스를 저장하고(초기값=0), `count`는 제거하는 돌섬의 개수를 저장한다. 2. `i` 첫번째 돌섬부터 순차적으로 탐색하며 제거할 돌섬을 찾는다. 1. `pt`번째 돌섬에서 `i`번째 돌섬으로 가는 거리가 `mid`보다 크거나 같은 경우 `mid`가 점프하는 최소거리의 최댓값이 될 수 있으므로 학생들을 점프시킨다. `pt`값을 `i`로 갱신한다. 2. `pt`번째 돌섬에서 `i`번째 돌섬으로 가는 거리가 `mid`보다 작은 경우 `mid`가 점프하는 최소거리의 최댓값이 될 수 없으므로 거리를 늘리기 위해 돌섬을 제거한다. `count`값을 1 올린다. 3. `count`가 `M`보다 크다면 제거해야할 돌섬 수보다 많이 제거한 것이므로 거리의 폭을 줄인다. `end`에 `mid-1`을 저장한다. 4. `count`가 `M`보다 작거나 같다면 돌섬을 조건에 맞게 잘 제거한 것이므로 `answer`에 `mid`를 저장한다. 그리고 `start`에 `mid+1`을 저장한다. 3. `answer`를 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int D = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] rockIslands = new int[N + 1];
for (int i = 1; i <= N; i++)
rockIslands[i] = Integer.parseInt(br.readLine());
Arrays.sort(rockIslands);
int start = 0;
int end = D;
int answer = 0;
while (start <= end) {
int mid = (start + end) / 2;
int pt = 0, count = 0;
for (int i = 1; i <= N; i++) {
if (mid <= rockIslands[i] - rockIslands[pt]) {
pt = i;
} else {
count++;
}
}
if (count > M) {
end = mid - 1;
} else {
answer = mid;
start = mid + 1;
}
}
System.out.println(answer);
}
}
N개의 시험지를 현재 순서 그대로 K개의 그룹으로 나눈 뒤 각각의 그룹에 맞은 문제 개수의 합을 구하여 그 중 최솟값을 시험 점수로 하기로 하였다. 현수가 이번 시험에서 받을 수 있는 최대 점수를 계산하는 프로그램을 작성하자.
입력
첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 ≤ K ≤ N ≤ 10^5)
두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 ≤ x ≤ 20)
출력
현수가 받을 수 있는 최대 점수를 출력한다.
🍥 풀이
8 2
12 7 19 20 17 14 9 10
이분탐색을 활용하여 정답을 찾아낼 수 있다.
이분탐색 시작값을 0, 끝값을 2000000(N의 최댓값*x의 최댓값)으로 설정해도 되고, 시작값은 맞은 시험 개수 최솟값인 '7'과 끝값은 전체 맞은 개수의 총합인 '108'로 설정해도 된다. 후자로 설정하면 이분탐색 실행 횟수를 줄일 수 있다.
시작값을 7, 끝값을 108로 설정한다면, mid값은 (108+7)/2 = 57이 될 것이다.
시험지 순서대로 처음부터 57 이상이 될 때까지 더해가며 그룹을 만들면, 그룹은 1개가 만들어진다.
[17, 14, 9, 10]은 합이 50이므로 그룹으로 만들 수 없다.
그룹은 2개로 구성되어야 하는데, 1개만 만들어졌다. 그룹 수를 늘리기 위해서는 mid값을 줄여야한다!
mid를 줄이기 위해서는 끝값을 줄여야하고, 끝값을 mid-1로 갱신한다.
시작값을 7, 끝값이 56일 때, mid값은 31이 되고, 그룹은 3개가 만들어진다.
아까와는 반대로 그룹 수를 줄이기 위해서는 mid값을 늘려야한다! mid를 늘리기 위해서는 시작값을 늘려야하고, 시작값을 mid+1로 갱신한다.
시작값을 32, 끝값이 56일 때, mid값은 44이 되고, 그룹은 2개가 만들어진다.
그룹이 2개가 만들어졌지만, 44가 그룹 2개로 만들 수 있는 최대 점수라고 장담할 수 없다!
mid값을 늘려서 그룹 2개로 만들 수 있는 최댓값인지 확인한다. 시작값을 mid+1로 갱신한다.
계속 이분탐색을 하다보면,, 시작값이 51, 끝값이 52가 되는 경우가 나온다. mid값은 51이 되고, 그룹은 1개가 만들어진다.
그룹 수를 늘리기 위해서 끝값을 mid-1로 갱신한다.
시작값은 51, 끝값은 50이 되므로 이분탐색은 종료된다. 끝값을 기준으로 그룹을 만들어보면 2개가 만들어 지는 걸 확인할 수 있다.
이분 탐색 실행이 종료되면, 끝값이 그룹이 K개가 만들어질 때 최대 점수가 된다.
1. 시작값(0)과 끝값(20*100000)을 넣어 binarySearch 함수를 호출한다. 2. binarySearch 함수에서 이분탐색을 진행한다. 1. `mid`는 그룹별로 맞은 문제 개수 중 최소값을 나타내며, `start`와 `end`의 평균값을 저장한다. 2. `sum`은 그룹별로 맞은 문제 개수를 저장하고, `groupCount`는 그룹수를 저장한다. 3. `n` 첫번째 시험지부터 순차적으로 탐색하며 그룹을 묶는다. 1. `sum`에 현재 시험지에서 맞은 문제 개수를 더한다.(score[n]) 2. 만약 `mid`보다 `sum`이 크거나 같은 경우, 그룹을 만드는 조건에 부합하므로 `sum`을 0으로 초기화시키고 `groupCount`에 1을 더한다. 4. `groupCount`가 `K`보다 크거나 같은 경우, 그룹별로 맞은 문제 개수 중 최소값이 현재보다 커야한다. 그러므로 `start`값을 `mid+1`로 갱신한다. 5. `groupCount`가 `K`보다 작은 경우, 그룹별로 맞은 문제 개수 중 최소값이 현재보다 작아야한다. 그러므로 `end`값을 `mid-1`로 갱신한다. 6. 이분탐색이 끝났다면, `end`를 반환하며 binarySearch 함수를 종료한다. 3. binarySearch 함수 반환값을 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, K;
static int[] score;
public static void main(String[] args) throws Exception {
init();
System.out.println(binarySearch(0, 2000000));
}
static void init() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
score = new int[N];
for (int n = 0; n < N; n++) {
score[n] = Integer.parseInt(st.nextToken());
}
}
static int binarySearch(int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
int sum = 0, groupCount = 0;
for (int n = 0; n < N; n++) {
sum += score[n];
if (mid <= sum) {
sum = 0;
groupCount++;
}
}
if (K <= groupCount) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return end;
}
}
💫 리뷰
제자리 멀리뛰기 문제랑 접근 방식이 비슷해서 어렵지않게 풀 수 있었다.
<이분 탐색> 문제를 선택해서 풀었던거라,, 코테가서 이런 문제가 나왔을때 바로 이분 탐색을 떠올릴 수 있을지는 모르겠다..@_@
길이가 N 미터이고, 높이가 H 미터인 동굴에 석순과 종유석이 번갈아가면서 있다. (N은 짝수이고, 석순 먼저 나타난다.)
개똥벌레가 한 구간을 정해 날아가면서 만나는 장애물들을 파괴한다.
개똥벌레가 파괴하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)
다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.
출력
첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.
🤔 풀이
6 7
1
5
3
3
5
1
위와 같은 입력이 들어왔다고 한다면, 동굴은 아래와 같은 그림이 될 것이다.
개똥벌레가 'h'높이로 날아간다고 하면, 석순은 `h`높이 이상인 석순의 수를 카운트하면 된다.
반면, 종유석은 위에서 내려오기 때문에 H-`h`+1 높이 이상인 종유석의 수를 카운트해야 한다.
즉, 개똥벌레가 'h' 높이로 날아가는 경우 높이가 h 이상인 석순과 H-h+1 이상인 종유석의 수를 더하면 개똥벌레가 부딪히는 장애물의 수가 된다.
높이가 x보다 큰 석순과 종유석을 구하기 위해서 누적합을 활용했다.
입력을 받으면서 석순과 종유석 높이에 해당하는 인덱스에 1을 더하고, 입력을 다 받은 후에 인덱스 내림차순으로 누적합을 했다.
1. 석순(`A`)와 종유석(`B`)를 순서대로 입력받는다. 2. 입력을 다 받은 후 석순과 종유석 배열 모두 누적합을 계산한다. 3. 동굴의 모든 높이를 확인하면서 해당 높이에 있는 석순과 종유석의 개수를 구한다. 4. 개똥벌레가 부딪히는 장애물 최솟값과 구간 수를 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine().trim();
int N = Integer.parseInt(input.substring(0, input.indexOf(' ')));
int H = Integer.parseInt(input.substring(input.indexOf(' ') + 1));
int[] A = new int[H + 1];
int[] B = new int[H + 1];
for (int n = 0; n < N; n += 2) {
A[Integer.parseInt(br.readLine())]++;
B[Integer.parseInt(br.readLine())]++;
}
for (int h = H - 1; 0 < h; h--) {
A[h] += A[h + 1];
B[h] += B[h + 1];
}
int count = 0;
int min = N;
for (int h = H; 0 < h; h--) {
if (A[h] + B[H - h + 1] < min) {
count = 1;
min = A[h] + B[H - h + 1];
} else if (A[h] + B[H - h + 1] == min) {
count++;
}
}
System.out.println(min + " " + count);
}
}
💫 리뷰
이분 탐색을 공부하기 위해 선택한 문제였는데,, 이분 탐색을 활용하지 않고 푸는게 시간이 더 짧았다..! w(°ｏ°)w
