[이코테] 실전 문제

이진 탐색 문제는 left, right를 정하고 mid값을 비교해가며 풀면 된다. 이진 탐색 문제를 풀 때 배열은 항상 정렬되어 있어야 한다.

 

부품 찾기

배열 N 에서 배열 M의 값들을 찾는 문제였다. 

 

배열 N의 값들을 오름차순으로 정렬한 후 M의 값들을 차례대로 이진탐색한 결과를 출력했다. 또, 찾아야 하는 값을 findNum으로 두고 초기 left와 right 값은 각각 0과 N 배열의 최댓값의 index인 N-1로 정했다.

 

이진탐색을 할 때 총 4가지 경우가 있다.

• narr[mid] 값이 findNum 보다 클 경우 → 왼쪽 범위를 탐색해야 함 (right 값을 mid-1로 바꿔줌)
• narr[mid] 값이 findNum 보다 작을 경우 → 오른쪽 범위를 탐색해야 함 (left 값을 mid+1 로 바꿔줌)
• 같을 경우 → 탐색 완료
• 반복문을 빠져나왔을 때 left>right 인 경우 → 찾는 값이 없음

int narr[1000001];
int marr[100001];

int main() {
	
	int N, M;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &narr[i]);
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d", &marr[i]);
	}

	sort(narr, narr + N);

	int findNum, left, right, mid;

	for (int i = 0; i < M; i++) {
		findNum = marr[i];

		left = 0;
		right = N - 1;
		while (left<=right) {
			mid = (left + right) / 2;
			if (narr[mid] > findNum) {				
				right = mid-1;
			}
			else if (narr[mid] < findNum) {				
				left = mid + 1;				

			}
			else {
				printf("yes ");
				break;
			}						
		}
		if (left > right) printf("no ");
	}
}

/*
5 
8 3 7 9 2 
3 
5 7 9
*/

 

---

 

떡볶이 떡 만들기

떡의 개수 N이 주어지고 요청한 떡의 길이 M, 떡의 개별 높이가 주어진다. 절단기에 높이를 설정하면 그 높이보다 긴 떡만 잘리고, 잘린 떡의 길이가 M과 같아야 한다(같을 수 없다면 커야 한다). 떡을 자르는 높이의 최댓값을 구하는 문제였다.

 

이 문제는 풀이 방법을 생각해내기가 조금 어려웠다. 앞의 문제처럼 숫자 중에서 찾는 문제가 아니었고 범위를 계산하는 문제였는데, 떡의 길이를 그래프로 그리면 접근하기 쉬워진다. 책에서는 가로로 그래프를 그렸는데 나는 세로로 그렸다.

 

이 그래프에서 하늘색 글자는 무시해도 된다. 그래프의 왼쪽 0과 19는 자를 수 있는 높이의 범위로, 0부터 떡 배열의 최댓값(문제에서는 19)까지이다. left를 0, right를 19로 설정하면 mid 값은 9가 되며 그래프의 빨간 선으로 표시해놨다. 이 선으로 잘린 떡들의 길이를 더해주면 되는데 이 길이가 M보다 크다면 더 높게 잘라야 하고 M보다 작으면 더 낮게 잘라야 한다. 

 

문제에서 적어도 M만큼의 떡의 길이를 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하라고 했다. 더해준 길이와 M이 같을 수 없으면 M보다 큰 길이로 자를 수 있는 절단기의 높이 중 가장 큰 값이 답이 된다.

int N;
int M;
int length[1000001];

int main() {
	scanf("%d %dd", &N, &M);

	for (int i = 0; i < N; i++) {
		scanf("%d", &length[i]);
	}

	sort(length, length + N);

	int left, right, mid;
	int maxLength = 0, sum = 0, diff;	
	left = 0;
	right = length[N - 1];

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

		for (int i = 0; i < N; i++) {
			diff = length[i] - mid;
			if (diff > 0) sum += diff;
		}

		if (M < sum) { //더 큰 값으로 잘라줘야 함
			if (maxLength < mid) {
				maxLength = mid;
			}
			left = mid + 1;
		}
		else if (M > sum) {
			right = mid - 1;
		}
		else {
			maxLength = mid;
			break;
		}		
	}
	printf("%d", maxLength);
	
}

/*
4 6 
19 15 10 17
*/

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24