<stdio.han>

[문제 링크]

https://www.acmicpc.net/problem/4158

[난이도]

- Silver 5

[알고리즘]

- 이분탐색

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, answer;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            if (N == 0 && M == 0) break;

            arr = new int[N];
            answer = 0;

            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(br.readLine());
            }

            for (int i = 0; i < M; i++) {
                int key = Integer.parseInt(br.readLine());
                if (binarySearch(key)) {
                    answer++;
                }
            }

            System.out.println(answer);
        }

        br.close();
    }

    static boolean binarySearch(int key) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (key == arr[mid]) {
                return true;
            } else if (key < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}

[풀이]

가장 기본적인 이분탐색 코드이다.

key 값을 찾을 때마다 answer++를 한 후 출력해준다.

[문제 링크]

https://www.acmicpc.net/problem/2417

[난이도]

- Silver 4

[알고리즘]

- 이분 탐색

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static long n, answer = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Long.parseLong(br.readLine());
        binarySearch(n);
        System.out.println(answer);
    }

    static void binarySearch(long key) {
        long left = 0;
        long right = key;
        while (left <= right) {
            long mid = (left + right) / 2;
            if (key <= Math.pow(mid, 2)){
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }
}

[풀이]

이분탐색 알고리즘 보다 타입맞추는게 더 까다로웠다.

(mid * mid) 로 계산하면 long의 범위를 넘어가 버려 정답을 맞출 수 없다.

Math.pow(mid, 2) 는 반환값이 double 이기때문에 이를 사용해야한다.

[문제 링크]

https://www.acmicpc.net/problem/1654

[난이도]

- Silver 2

[알고리즘]

- 파라메트릭 서치

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int K, N;
    static long left = 1, right = Integer.MIN_VALUE;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new int[K];

        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            right = Math.max(right, arr[i]);
        }

        parametricSearch();

        br.close();
    }
    static void parametricSearch() {
        while (left <= right) {
            long mid = (left + right) / 2;
            long LAN = 0;
            for (int i = 0; i < arr.length; i++) {
                LAN += (arr[i] / mid);
            }
            if (LAN>=N){
                left = mid + 1;
            } else if (LAN < N) {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

[풀이]

- left, right, mid 를 long으로 설정해주어야 한다.

- left의 최소값이 1이어야 한다. 그렇지 않으면 divide by zero 오류가 발생한다. 예를들어 모든 가지고있는 랜선의 길이가 1이고 left가 0일 경우 mid가 0이 된다.

API를 쓸모 있게 하려면 잘 작성된 문서도 곁들여야 한다. API를 올바로 문서화하려면 공개된 모든 클래스, 인터페이스, 메서드, 필드 선언에 문서화 주석을 달아야 한다.

• 메서드용 문서화 주석에는 해당 메서드와 클라이언트 사이의 규약을 명료하게 기술해야 한다.

• 제네릭 타입이나 제네릭 메서드를 문서화할 때는 모든 타입 매개변수에 주석을 달아야 한다.

/**
 * 제네릭 스택 클래스.
 *
 * @param <E> 스택에 저장할 요소의 타입
 */
public class GenericStack<E> {
    private List<E> elements = new ArrayList<>();

    /**
     * 스택에 요소를 추가합니다.
     *
     * @param element 추가할 요소
     */
    public void push(E element) {
        elements.add(element);
    }

    /**
     * 스택에서 요소를 제거하고 반환합니다.
     *
     * @return 제거된 요소
     * @throws EmptyStackException 스택이 비어 있는 경우
     */
    public E pop() {
        if (elements.isEmpty()) {
            throw new EmptyStackException();
        }
        return elements.remove(elements.size() - 1);
    }
}

• 열거 타입을 문서화할 때는 상수들에도 주석을 달아야 한다.

• 애너테이션 타입을 문서화할 때는 멤버들에도 모든 주석을 달아야 한다.

• 클래스 혹은 정적 메서드가 스레드 안전하든 그렇지 않든, 스레드 안전 수준을 반드시 API 설명에 포함해야 한다.

핵심 정리 : 문서화 주석은 여러분 API를 문서화하는 가장 훌륭하고 효과적인 방법이다. 공개 API라면 빠짐없이 설명을 달아야 한다. 표준 규약을 일관되게 지키자. 문서화 주석에 임의의 HTML태그를 사용할 수 있음을 기억하라. 단, HTML 메타문자는 특별하게 취급해야 한다.

• Opional을 반환하는 메서드에서는 절대 null을 반환하지 말자.
• 컬렉션, 스트림, 배열, 옵셔널 같은 컨테이너 타입은 옵셔널로 감싸면 안 된다.
• 옵셔널을 반환값이 아닌 필드나 다른 용도로 사용하지 말자.

메서드 반환 타입을 T 대신 Optional<T>로 선언해야 하는 기본 규칙 : 

• 결과가 없을 수 있으며, 클라이언트가 이 상황을 특별하게 처리해야 한다면 Optional<T>를 반환한다.

핵심 정리 : 값을 반환하지 못할 가능성이 있고, 호출할 때마다 반환값이 없을 가능성을 염두에 둬야하는 메서드라면 옵셔널을 반환해야 할 상황일 수 있다. 하지만 옵셔널 반환에는 성능 저하가 뒤따르니, 성능에 민감한 메서드라면 null을 반환하거나 예외를 던지는 편이 나을 수 있다. 그리고 옵셔널을 반환값 이외의 용도로 쓰는 경우는 매우 드물다.

메서드에서 컬렉션이나 배열을 반환할 때, null이 아닌 빈 컬렉션이나 빈 배열을 반환해야 하는데 그 이유는

1. 호출자 코드 단순화 : 호출자가 null을 처리할 필요 없이 바로 컬렉션이나 배열을 사용할 수 있다.
2. 널 포인터 예외 방지 : null을 반환할 경우 이를 처리하지 않아 발생할 수 있는 NullPointerException을 방지할 수 있다.
3. 일관성 유지 : 항상 같은 타입의 객체를 반환하므로 메서드 사용이 일관되고 예측가능해진다.

핵심 정리 : null이 아닌, 빈 배열이나 컬렉션을 반환하라. null을 반환하는 api는 사용하기 어렵고 오류 처리 코드도 늘어난다. 그렇다고 성능이 좋은 것도 아니다.

가변인수 : 메서드에 전달하는 인수의 개수를 유연하게 할 수 있는 편리한 기능.

장점 : 유연성, 가독성

단점 :

• 오버로드의 모호성 : 메서드 오버로드 시 가변인수가 다른 오버로드된 메서드와 충돌할 수 있다
• 성능 : 가변인수는 배열로 변환되기 때문에 성능에 약간의 오버헤드가 있다.
• 타입 안정성 : 컴파일 타임에 타입 안정성이 완전히 보장되지 않는다.

핵심 정리 : 인수 개수가 일정하지 않은 메서드를 정의해야 한다면 가변인수가 반드시 필요하다. 메서드를 정의할 때 필수 매개변수는 가변인수 앞에 두고, 가변인수를 사용할 때는 성능 문제까지 고려하자.

다중정의 : 메서드 이름은 같지만 매개변수의 타입이나 개수가 다른 여러 메서드를 정의하는 것.

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);
    }
}

모든 다중정의된 메서드가 동일한 동작을 하도록 만든다.

핵심정리 : 프로그래밍 언어가 다중정의를 허용한다고 해서 다중정의를 꼭 활용하라는 뜻은 아니다. 일반적으로 매개변수 수가 같을 때는 다중정의를 피하는게 좋다. 상황에 따라, 특히 생서자라면 이 조언을 따르기가 불가능할 수 있다. 그럴 때는 헷갈릴 만한 매개변수는 형변화하여 정확한 다중정의 메서드가 선택되도록 해야 한다. 이거싱 불가능하면, 예컨대 기존 클래스를 수정해 새로운 인터페이스를 구현해야 할 때는 같은 객체를 입력받는 가중정의 메서드들이 모두 동일하게 동작하도록 만들어야 한다. 그렇지 못하면 프로그래머들은 다중정의된 메서드나 생성자를 효과적으로 사용하지 못할 것이고, 의도대로 동작하지 않는 이유를 이해하지도 못할 것이다.