✔ 수 찾기
문제 분석하기
N의 범위가 100000이므로 단순 반복문으로는 문제를 풀 수 없음
이진 탐색을 적용하면 O(MlogN) 시간 복잡도로 해결할 수 있으며, 자바의 기본 정렬을 사용하더라도 O(NlogN) 시간 복잡도를 가짐
손으로 풀어보기
- 탐색 데이터를 1차원 배열에 저장한 다음 저장된 배열을 정렬
- X라는 정수가 존재하는지 이진 탐색을 사용해 확인
슈도코드 작성하기
N(정렬할 수 개수) M(탐색할 숫자의 개수)
A(정렬할 배열 선언하기)
for(N의 개수만큼 반복하기)
{
A 배열 저장하기
}
A 배열 정렬하기
for(M의 개수만큼 반복하기)
{
target(찾아야 하는 수)
start(시작 인덱스)
end(종료 인덱스)
while(시작 인덱스 <= 종료 인덱스) {
midi(중간 인덱스)
if(중앙값 > target) {
종료 인덱스 = 중간 인덱스 - 1
}
else if(중앙값 < target) {
시작 인덱스 = 중간 인덱스 + 1
} else {
찾았으므로 반복문 종료하기
}
}
if(찾았음) 1 출력
else 0 출력
}
코드 구현하기
/**
* 1920) 수_찾기
*/
public class D029_1920 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N(정렬할 수 개수)
int N = sc.nextInt();
// A(정렬할 배열 선언하기)
int[] A = new int[N];
for (int i = 0; i < N; i++) {
// A 배열 저장하기
A[i] = sc.nextInt();
}
// A 배열 정렬하기
Arrays.sort(A);
// M(탐색할 숫자의 개수)
int M = sc.nextInt();
for (int i = 0; i < M; i++) {
boolean find = false;
// target(찾아야 하는 수)
int target = sc.nextInt();
// start(시작 인덱스)
int start = 0;
// end(종료 인덱스)
int end = A.length - 1;
while (start <= end) {
// midi(중간 인덱스)
int midi = (start + end) / 2;
int midV = A[midi];
if (midV > target) {
end = midi - 1;
} else if (midV < target) {
start = midi + 1;
} else { // 찾았으므로 반복문 종료하기
find = true;
break;
}
}
// if(찾았음) 1 출력
if (find) {
System.out.println(1);
} else { // else 0 출력
System.out.println(0);
}
}
}
}
'Coding Test > 알고리즘 실전' 카테고리의 다른 글
[1929] 소수 구하기 (0) | 2023.07.04 |
---|---|
[11047] 동전 0 (0) | 2023.07.04 |
[2178] 미로 탐색 (0) | 2023.07.03 |
[11724] 연결 요소의 개수 (0) | 2023.07.03 |
[1427] 소트인사이드 (0) | 2023.06.30 |