개발일지/Algorithm
백준 - 10815 숫자 카드 [이분탐색]
E-room
2023. 10. 24. 23:37
728x90
10815번: 숫자 카드
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
1. 문제 요약
숫자 배열이 주어지고, 찾고자 하는 숫자가 주어졌을 때, 찾고자 하는 숫자가 배열에 존재하는지 판단하시오.
2. 접근 방법
이분 탐색 알고리즘을 사용합니다.
해당 알고리즘은 일반적으로 하는 up down 게임과 같은 원리입니다.
정렬된 상태에서 절반씩 소거하며 찾아내는 방법입니다.
오름차순으로 정렬된 배열에서 중간 부분을 탐색하고,
찾고자 하는 숫자보다 크면 해당 지점부터 끝부분까지의 중간 부분을 탐색합니다.
찾고자 하는 숫자보다 작으면 이전에 탐색했던 부분의 절반 아랫부분을 탐색합니다.
위 과정을 반복하여 찾아내는 방법입니다.
- 숫자 배열을 오름차순으로 정렬합니다.
- 배열의 중간 지점을 방문합니다.
- 찾으려는 숫자보다 클 경우, 해당 숫자를 포함하여 아랫부분은 제외하고 다시 중간 지점을 방문합니다.
- 찾으려는 숫자보다 작을 경우, 해당 숫자를 포함하여 윗부분은 제외하고 다시 중간 지점을 방문합니다.
- 위 과정을 더 이상 반복할 수 없을때까지 반복하고, 숫자를 찾으면 종료합니다.
3. 파이썬
def solution(n, cards, m, nums):
cards.sort()
for num in nums:
s = 0
e = n - 1
isFind = False
while s <= e:
index = (s + e) // 2
# up
if num > cards[index]:
s = index + 1
# down
elif num < cards[index]:
e = index - 1
# answer
else: # num == cards[index]:
isFind = True
break
if isFind:
print('1', end=' ')
else:
print('0', end=' ')
4. 자바
private static void solution(int n, int[] cards, int[] nums) {
Arrays.sort(cards);
StringBuilder answer = new StringBuilder();
for (int num : nums) {
int s = 0;
int e = n - 1;
boolean isFind = false;
while (s <= e) {
int index = (s + e) / 2;
if (num > cards[index]) { // up
s = index + 1;
} else if (num < cards[index]) { // down
e = index - 1;
} else { // answer
isFind = true;
break;
}
}
answer.append(isFind ? "1 " : "0 ");
}
System.out.println(answer);
}
5. 전체 코드
728x90