https://www.acmicpc.net/problem/19637
19637번: IF문 좀 대신 써줘
첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭
www.acmicpc.net
코드설명
이분탐색 문제입니다.
이 문제는, 이 문제가 이분탐색인것을 떠올리는것이 어려웠습니다.
문제를 어떻게 풀지 어려웠던 이유는, 이 문제는 범위와 함꼐 문제가 주어졌습니다. 이전에는 이분탐색을 단순히 정확히 일치하는 Target 값이나 비슷한 값만 검색하는 문제를 주로 겪어보았기에 익숙치 않았던 것 같습니다. 예를들어, 이 문제의 예제의 경우 10000, 1000000, 10000000 이런식으로 칭호와 점수기준으로 그 사이의 값을 찾는것이기에 생각하기가 어려웠던 것 같 습니다.
처음에 문제를 보고, HashMap 문제인가 라는 생각이 들었습니다.
하지만, HashMap을 구현해서 진행하려 보니, N은 10^5, M 도 10^5 개의 개수이기에, 만일, 직접 순회하면서 범위를 찾는다면 최악의 경우 10^10의 시간복잡도가 나오게됩니다. 이는 100억으로, 시간초과가 반드시 발생합니다.
주어진 칭호들을 사용자의 점수가 이분탐색으로 순회하며 진행합니다.
기본적인 문제 푸는 방식은, 주어진 칭호들을 캐릭터가 이분탐색으로 순회하면서 진행합니다.
시간복잡도를 확인해보면, 만약에 칭호들을 순회하면서 해당 값들을 찾을경우 칭호의 개수는 1 <= N <= 10^5 이고, 또 칭호를 출력해야한는 캐릭터들의 개수는 M (1 <= M <= 10 ^5) 이기에 최악의 경우 10^10 이 나옵니다.
그렇기에 이분탐색을 통해 O(M log N)의 시간복잡도를 만들어서 해결할 수 있습니다.
문제에서 헷갈리는점은, 이분탐색에서 범위선정입니다.
//target보다 더 크거나 같다면, 더 작은 값으로 검색이동합니다.
//같은경우까지 고려하는 이유는,
if(target <= energy[middle]) {
right = middle - 1;
}주어진 칭호들을 통해 각 회원들의 target값의 적절한 위치를 찾아야하는데,
이때 회원들의 target값이 energy[middle]값보다 작거나 같다면, energy[middle]은 그 Index보다 더 작아져야만 합니다.
이를 통해, 만약에 같은경우라면 middle값을 다시 한번 감소시키면서 가장 작은값을 구할 수 있습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K = 0;
public static int answer = 0;
public static String[] name;
public static int[] energy;
public static int[] arr;
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
name = new String[N];
energy = new int[N];
arr = new int[M];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
name[i] = st.nextToken();
energy[i] = Integer.parseInt(st.nextToken());
}
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
arr[i] = Integer.parseInt(st.nextToken());
binarySearch(arr[i]);
}
System.out.println(sb.toString());
}
public static void binarySearch(int target) {
int left = 0;
int right = N - 1;
while(left <= right) {
int middle = ( left + right ) / 2;
//target보다 더 크거나 같다면, 더 작은 값으로 검색이동합니다.
//같은경우까지 고려하는 이유는, 그래야만 포함되는 값을 찾을 수 있습니다.
if(target <= energy[middle]) {
right = middle - 1;
}
//target보다 작다면, 더 큰값을 찾아나섭니다.
else if(target > energy[middle]) {
left = middle + 1;
}
}
sb.append(name[right + 1]).append("\n");
}
}
정답코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N,M;
public static int[] arr;
public static Node[] node;
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
node = new Node[N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
String a = st.nextToken();
int b = Integer.parseInt(st.nextToken());
node[i] = new Node(a, b);
}
arr = new int[M];
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
arr[i] = a;
}
// Arrays.sort(arr); 해당코드 있을시 틀림, 정해져있는 순서대로 출력필요
for(int i=0;i<M;i++) {
binarySearch(arr[i]);
}
System.out.println(sb);
}
public static void binarySearch(int target) {
int start = 0;
int end = N-1;
while(start<=end) {
int middle = (start + end) / 2;
if( node[middle].fightScore >= target) { // 작거나 같아야 해당값까지 포함하여 검사
end = middle - 1;
}else {
start = middle + 1;
}
}
sb.append(node[end+1].name).append('\n');
// sb.append(node[start].name).append('\n');
}
}
class Node{
String name;
int fightScore;
public Node(String name, int fightScore) {
this.name = name;
this.fightScore = fightScore;
}
}
시간초과 난 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N,M;
public static int[] arr;
public static Node[] node;
public static int answer = 0;
public static int start = 0, end = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
node = new Node[N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
String a = st.nextToken();
int b = Integer.parseInt(st.nextToken());
node[i] = new Node(a, b);
}
arr = new int[M];
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
arr[i] = a;
}
// Arrays.sort(arr); 해당코드 있을시 틀림
for(int i=0;i<M;i++) {
binarySearch(arr[i]);
}
}
public static void binarySearch(int target) {
int start = 0;
int end = N-1;
while(start<=end) {
int middle = (start + end) / 2;
if( node[middle].fightScore >= target) { // 작거나 같아야 해당값까지 포함하여 검사
end = middle - 1;
}else {
start = middle + 1;
}
}
System.out.println(node[start].name); //end로 할경우 araryoutofindex, start로 처리해야합니다. 아니면end + 1
}
}
class Node{
String name;
int fightScore;
public Node(String name, int fightScore) {
this.name = name;
this.fightScore = fightScore;
}
}
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
private static int N, M, Q;
private static String[] name;
private static int[] arr;
private static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
name = new String[N];
arr = new int[N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
String str = st.nextToken();
int standard = Integer.parseInt(st.nextToken());
name[i] = str;
arr[i] = standard;
}
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int score = Integer.parseInt(st.nextToken());
// answer = binarySearch(0, (int) Math.pow(10, 9), score);
answer = binarySearch(0, arr.length - 1, score);
System.out.println(name[answer]);
}
}
private static int binarySearch(int lo, int hi, int target) {
int left = lo - 1;
int right = hi + 1;
while(left + 1 < right) {
int mid = (left + right) / 2;
if( arr[mid] < target) {
left = mid;
} else if(arr[mid] >= target) {
right = mid;
}
}
return right;
}
}'알고리즘 > binary_search' 카테고리의 다른 글
| [백준] 2805 나무 자르기 - 파라매트릭 서치(Paramatric Search) JAVA (0) | 2023.07.27 |
|---|---|
| [백준] 2512 예산 - 파라매트릭 서치(Paramatric Search) JAVA (0) | 2023.07.27 |
| [백준] 2512 예산 - 파라메트릭 서치(Paramatric Search) JAVA (0) | 2023.07.27 |
| [백준] 2417 정수 제곱근 - 이분탐색(binary search) JAVA (0) | 2023.07.26 |
| [백준] 10815 숫자 카드 - 이분탐색(binary search) JAVA (0) | 2023.07.26 |