백준 1920 - Silver 4
https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다.
다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다.
다음 줄에는 M개의 수들이 주어지는데,
이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
예제입력
5
4 1 5 2 3
5
1 3 7 9 5예제출력
1
1
0
0
1
가장 쉽게 접근하는 방식으로 먼저 생각을 해보았다.
문제의 조건이 존재하는지의 여부만 파악하면 되는 것이기에
list.contains()함수를 활용하여 존재한다면 1 아니면 0을 출력하는 코드를 구현해보았다.
실버4의 문제이기에 이정도면 충분하지 않을까?
라는 생각에 쉬운 코드로 접근했던 것 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0;i<n;i++) list.add(sc.nextInt());
int m = sc.nextInt();
int[] arr = new int[m];
for(int i = 0;i<m;i++) {
arr[i] = sc.nextInt();
}
StringBuilder sb = new StringBuilder();
for(int i = 0;i<arr.length;i++) {
if(list.contains(arr[i])) sb.append(1).append("\n");
else sb.append(0).append("\n");
}
sc.close();
System.out.println(sb);
}
}
|
cs |
하지만 예상과는 다르게 시간초과가 나왔다.
그래서 생각을 해보았다. 어차피 값을 넣고 체크를 하려면 n만큼의 시간복잡도가 필요하다.
그럼에도 불구하고 시간초과가 나온다는 것은
log n 혹은 1과 같은 n보다 짧은 시간복잡도를 가진 알고리즘이 필요했다.
그 중의 하나가 이분탐색이다.
이분탐색은 정렬된 배열을 토대로 중간값을 정하고 Key값이 있는지를 찾는 것이다.
먼저 중앙값을 지정하기 위해서 left = 0 / right = 배열의 크기로 지정한 다음
mid라는 변수를 선언하여서 중앙값을 찾는다.
만약 찾는 Key값이 arr[mid]보다 크다면 left = mid+1 작다면 right = mid-1을 해준다.
그렇게 찾다가 답을 찾지 못하는 경우를 대비해서 while문을 다음과 같이 사용한다.
while(left <= right)
예를 들어서 int[] arr = {1,3,4,6,7} 의 배열에서 6을 찾는 것을 생각해보자.
| left | right | mid | arr[mid] |
| 0 | 4 | 2 | 4 |
| 3 | 4 | 3 | 6 |
예제입력을 예로 들었을 경우 원래 n만큼 즉 5번을 돌아야 답을 출력할 수 있었는데, 2번만에 답을 출력해낸다.
이처럼 시간복잡도를 줄이면서 효율적으로 문제를 풀 수 있는 방법도 있다는 것에 대해서 알려주는 문제였던 것 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int[] arr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine()," ");
arr = new int[n];
for(int i = 0;i<n;i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int m = Integer.parseInt(br.readLine());
Arrays.sort(arr);
st = new StringTokenizer(br.readLine()," ");
StringBuilder sb = new StringBuilder();
for(int i = 0;i<m;i++) {
if(BinarySearch(Integer.parseInt(st.nextToken()))>=0) {
sb.append(1).append("\n");
}else {
sb.append(0).append("\n");
}
}
System.out.println(sb);
}
public static int BinarySearch(int key) {
int low = 0;
int high = arr.length-1;
while(low <= high) {
int mid = (low+high)/2;
if(key < arr[mid]) {
high = mid-1;
}
else if(key > arr[mid]) {
low = mid+1;
}else {
return 1;
}
}
return -1;
}
}
|
cs |
'백준' 카테고리의 다른 글
| 백준 5430 (Java) AC (0) | 2023.06.28 |
|---|---|
| 백준 10026 (Java) 적록색약 (0) | 2023.06.27 |
| 백준 9095 (Java) 1, 2, 3 더하기 (0) | 2023.06.26 |
| 백준 10816 (Java) 숫자 카드 2 (0) | 2023.06.24 |
| 백준 1764 (Java) 듣보잡 (0) | 2023.06.24 |