[이코테] Chapter 7. 이진탐색 (java)

📍개념

1. 순차탐색

• 리스트 안에  있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 리스트가 정렬되어 있지 않을 때 사용
• O(N)

public static int sequantialSearch(int n, String target, String[] arr) {
		for (int i = 0; i < n; i++) {
			if (arr[i].equals(target))
				return i + 1;
		}
		return -1;
	}

---

2. 이진탐색

• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 데이터 찾는 방법
• 데이터가 이미 정렬돼 있을 때 사용
• O(logN)

1. 재귀함수로 구현한 결과

public static int binarySearch(int[] arr, int target, int start, int end) {
		if (start > end)
			return -1;
		int mid = (start + end) / 2;
		if (arr[mid] == target)
			return mid;
		else if (arr[mid] > target)
			return binarySearch(arr, target, start, mid - 1);
		else
			return binarySearch(arr, target, mid + 1, end);
	}

2. 반복문으로 구현한 결과

public static int binarySearch(int[] arr, int target, int start, int end) {
		while (start <= end) {
			int mid = (start + end) / 2;
			if (arr[mid] == target)
				return mid;
			else if (arr[mid] > target)
				end = mid - 1;
			else
				start = mid + 1;
		}
		return -1;
	}

---

📖 [예제 7-1] 부품 찾기

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.

N = 5
[8, 3, 7, 9, 2]

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M = 3
[5, 7, 9]

이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

입력 조건

• 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
• 셋째 줄에는 정수 M이 주어진다. (1 ≤ M ≤ 100,000)
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 10억 이하이다.

출력 조건

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

🔑 1. 이진 탐색으로 해결

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// 입력
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = sc.nextInt();
		int M = sc.nextInt();

		// 배열 정렬
		Arrays.sort(arr);

		// 각 원소 별로 이진탐색 진행 후 반환값이 -1이라면 no, 아니라면 yes 출력
		for (int i = 0; i < M; i++) {
			int target = sc.nextInt();
			if (binarySearch(arr, target, 0, N - 1) != -1)
				System.out.print("yes ");
			else
				System.out.print("no ");
		}
	}

	// 이진탐색 
	public static int binarySearch(int[] arr, int target, int start, int end) {
		while (start <= end) {
			int mid = (start + end) / 2;
			if (arr[mid] == target)
				return mid;
			else if (arr[mid] > target)
				end = mid - 1;
			else
				start = mid + 1;
		}
		return -1;
	}

}

🔑 2. 계수 정렬으로 해결

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// 입력
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = sc.nextInt();

		// 가장 큰 고유번호만큼 cnt 배열 생성
		Arrays.sort(arr);
		int[] cnt = new int[arr[arr.length - 1]];

		// 고유번호가 존재한다면 cnt 증가
		for (int i = 0; i < arr.length; i++) {
			cnt[arr[i] - 1]++;
		}

		int M = sc.nextInt();
		// cnt 배열에서 해당 부품 인덱스가 0이 아니라면 yes, 0이라면 no 출력
		for (int i = 0; i < M; i++) {
			int target = sc.nextInt();
			if (cnt[target - 1] != 0)
				System.out.print("yes ");
			else
				System.out.print("no ");
		}
	}
}

arr를 입력받을 때 배열의 크기를 1000001로 지정하여 cnt를 바로 입력받을 수도 있음 (참고)

🔑 3. 집합(set) 자료형으로 해결

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// 입력
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		HashSet<Integer> arr = new HashSet<>();
		for (int i = 0; i < N; i++)
			arr.add(sc.nextInt());
		int M = sc.nextInt();
		
		// target이 arr에 존재한다면 yes, 아니라면 no 출력 
		for (int i = 0; i < M; i++) {
			int target = sc.nextInt();
			if (arr.contains(target))
				System.out.print("yes ");
			else
				System.out.print("no ");
		}
	}
}

---

📖 [예제 7-2] 떡볶이 떡 만들기

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단기에 높이 H를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기를 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm 이다, 손님은 6cm만큼의 길이를 가져간다.

손님이 왔을 때 요청한 총 길이가 M일때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력 조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

🔑 풀이

베낌... 이진탐색인것까진 알겠는데 답이 이상함.. 9가 나옴 

end를 떡 높이 중에 제일 큰 값으로 둬서 그런가....

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// 입력
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] H = new int[N];
		for (int i = 0; i < N; i++) {
			H[i] = sc.nextInt();
		}

		int start = 0;
		int end = (int) 1e9; // 문제에서 주어진 최댓값
		int result = 0;
		// 이진탐색
		while (start <= end) {
			long total = 0;
			int mid = (start + end) / 2;
			// 남는 길이 계산 
			for (int i = 0; i < N; i++) {
				if (H[i] > mid)
					total += H[i] - mid;
			}
			if (total < M)
				end = mid - 1;
			else {
				result = mid;
				start = mid + 1;
			}
		}
		System.out.println(result);
	}
}