다중정의 : 메서드 이름은 같지만 매개변수의 타입이나 개수가 다른 여러 메서드를 정의하는 것.
public class Calculator {
// 두 개의 정수를 더하는 메서드
public int add(int a, int b) {
return a + b;
}
// 세 개의 정수를 더하는 메서드
public int add(int a, int b, int c) {
return a + b + c;
}
// 문자열을 더하는 메서드 (문자열 연결)
public String add(String a, String b) {
return a + b;
}
}
다중정의를 피할 수 없는 경우 :
매개변수 타입 변환
public class OverloadingExample {
public void print(String s) {
System.out.println("String: " + s);
}
public void print(Integer i) {
System.out.println("Integer: " + i);
}
public void print(Double d) {
System.out.println("Double: " + d);
}
}
매개변수 타입을 변환하여 명확하게 구분되도록 한다.
매개변수의 수가 같은 경우
public class OverloadingExample {
public void print(Object o1, Object o2) {
System.out.println("Object: " + o1 + ", " + o2);
}
public void print(String s1, String s2) {
print((Object) s1, (Object) s2);
}
public void print(Integer i1, Integer i2) {
print((Object) i1, (Object) i2);
}
}
모든 다중정의된 메서드가 동일한 동작을 하도록 만든다.
핵심정리 : 프로그래밍 언어가 다중정의를 허용한다고 해서 다중정의를 꼭 활용하라는 뜻은 아니다. 일반적으로 매개변수 수가 같을 때는 다중정의를 피하는게 좋다. 상황에 따라, 특히 생서자라면 이 조언을 따르기가 불가능할 수 있다. 그럴 때는 헷갈릴 만한 매개변수는 형변화하여 정확한 다중정의 메서드가 선택되도록 해야 한다. 이거싱 불가능하면, 예컨대 기존 클래스를 수정해 새로운 인터페이스를 구현해야 할 때는 같은 객체를 입력받는 가중정의 메서드들이 모두 동일하게 동작하도록 만들어야 한다. 그렇지 못하면 프로그래머들은 다중정의된 메서드나 생성자를 효과적으로 사용하지 못할 것이고, 의도대로 동작하지 않는 이유를 이해하지도 못할 것이다.
import java.io.*;
import java.util.*;
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));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] trees = new int[N];
st = new StringTokenizer(br.readLine(), " ");
int left = 0;
int right = -1;
for (int i = 0; i < N; i++) {
trees[i] = Integer.parseInt(st.nextToken());
right = Math.max(right, trees[i]); // 나무의 최대 높이 이상으로는 자를 수 없기때문에 최대값 구하기
}
while (left <= right) { // left가 right를 넘어서기 전까지 반복
int mid = (left + right) / 2;
long tree = 0; // 범위를 초과해서 long
for (int i = 0; i < N; i++) {
if (trees[i] > mid) {
tree += trees[i] - mid;
}
}
if (tree >= M) { // 너무 많이 가져갔거나 정확히 가져갔을 경우
left = mid + 1;
} else if (tree < M) { // 너무 적게 가져갔을 경우
right = mid - 1;
}
}
System.out.println(right);
}
}
[풀이]
이진 탐색 : 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이.
파라메트릭 서치 : 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘.
import java.io.*;
import java.util.*;
public class Main {
static int T, N, M, answer;
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
answer = 0;
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
arr = new int[N];
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
arr[j] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
int key = Integer.parseInt(st.nextToken());
answer += binarySearch(key);
}
System.out.println(answer);
}
}
static int binarySearch(int key) {
int left = 0;
int right = N - 1;
while (left <= right) { // left가 right를 넘어서기 전까지 반복
int mid = (left + right) / 2;
if (key >= arr[mid]) { // key가 mid 와 같거나 클 경우
left = mid + 1;
} else if (key < arr[mid]) { // key가 mid 보다 작을 경우
right = mid - 1;
}
}
// left가 right를 넘어감
return N - right - 1;
}
}
[풀이]
for문을 적게 사용하고 싶어서 B를기준으로 이분탐색을 했다. A가 B를 먹을 수 있는 쌍을 구하는게 아닌 B가 A에게 먹힐 수 있는 쌍을 구했다.
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] arr, answer;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
arr = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
M = Integer.parseInt(br.readLine());
answer = new int[M];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < M; i++) {
int key = Integer.parseInt(st.nextToken());
int tmp = upperBound(key) - lowerBound(key);
bw.write(tmp + " ");
}
bw.flush();
bw.close();
br.close();
}
/**
* key 값이 배열 내에 없을 경우 lowerBound, upperBound 둘다 key 바로 앞의 숫자를 찾게된다. 결국 n - n = 0이 된다.
*/
static int lowerBound(int key) {
int left = 0;
int right = N;
while (left < right) { // left 와 right가 같아질 때 까지 반복
int mid = (left + right) / 2; // 중간 위치
/**
* key 값이 중간 위치의 값보다 작거나 같을 경우
* 중복 원소일 경우 가장 왼쪽값을 선택
*/
if (key <= arr[mid]) {
right = mid;
} else { // key가 중간 값보다 '클' 경우. key > arr[mid]
left = mid + 1;
}
}
return left;
}
static int upperBound(int key) {
int left = 0;
int right = N;
while (left < right) {// left 와 right가 같아질 때 까지 반복
int mid = (left + right) / 2; // 중간 위치
if (key < arr[mid]) { // key가 중간 값보다 작을 경우
right = mid;
} else { // key가 중간 보다 '크거나' '같을' 경우 key >= arr[mid]
left = mid + 1;
}
// left가 right를 넘어서는 순간 종료된다 == left가 key의 바로 다음 인덱스가 되는순간 종료된다.
}
return left;
}
}
[풀이]
배열안에 중복값이 들어있을 경우가 존재하기 때문에 그 ( 중복값의 가장 왼쪽 인덱스 - 중복값의 가장 오른쪽의 다음 인덱스 ) 를 계산해주어야 한다.
leftBound
찾으려는 key값이 중간 값보다 작거나 클 경우 right 값이 mid가 되고 그 이외의 경우에는 left = mid + 1이 된다. 이를 반복할 경우 left 와 right가 key값들의 가장 왼쪽인덱스가 된다.
rightBound
찾으려는 key값이 중간 값보다 작을 경우 right = mid가 되고 그 외의 경우에는 left = mid + 1이 된다. 이를 반복하다 보면 right는 key값들의 가장 오른쪽 인덱스, left는 key값들의 가장 오른쪽의 다음 인덱스가 된다.
만약 찾으려는숫자가 없을 경우 lowerBound, upperBound 둘다 배열 중 key값을 초과하는 값중 첫 인덱스를 가리키게 된다.
