[코딩테스트]이진탐색(떡볶이 떡 만들기)

책 '이것이 취업을 위한 코딩 테스트다'를

기반으로 공부하였습니다.

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

1. 떡볶이 떡 만들기

입력조건

- 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다.

- 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력조건

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

 

작성코드(JAVA)

package codetest1;

import java.util.*;

public class test10 {
	public static int n,m;
	public static int[] dduck;
	
	public static int binary_search(int num) {
		int start = 0;
		int end = dduck[n-1];
		int mid = 0;
		int result = 0;
		int mid2 = 0;
		while(start<=end) {
			mid = (start+end)/2;
			result = 0;
			for(int j=0;j<n;j++) {
				int temp = dduck[j]-mid;
				if(temp>0) {
					result+=temp;
				}
			}
			if(result<num) {
				end = mid-1;
				
			}
			else {
				start = mid +1;
				mid2 = mid;
			}
		}
		return mid2;
		
	}
	
	public static void main(String[] args) {
		Scanner kb= new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		dduck = new int[n];
		
		for(int i=0;i<n;i++) {
			dduck[i] = kb.nextInt();
		}
		Arrays.sort(dduck);
		
		System.out.println(binary_search(m));
	}
}

설명

- 해당 문제는 탐색문제입니다. 데이터를 1부터 최고로 긴 떡의 길이 만큼 하나하나씩 탐색해도 되지만 그렇게 되면 반복 횟수가 너무 많아지기 때문에 이진 탐색을 이용하여 수행횟수를 낮춥니다.