[백준] 1920번 수 찾기
https://www.acmicpc.net/problem/1920
문제
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을 출력
나의 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
StringBuilder sb = new StringBuilder();
for (int i=0; i<N; i++) {
sb.append(sc.next());
}
String str = sb.toString();
int M = sc.nextInt();
for (int i=0; i<M; i++) {
System.out.println(str.contains(sc.next())? 1 : 0);
}
}
}
처음엔 StringBuilder를 사용하여 답을 출력하는 코드를 작성했으나 시간초과되었다.
contains() 메서드를 사용했는데,
찾아보니 해당 메서드는 O(N*M)의 시간 복잡도(여기서는 O(5*5)를 가져 시간 초과를 유발한 것으로 보인다.
import java.util.*;
public class Main {
static int[] A;
public static int binarySearch(int start, int end, int target) {
int mid = (start + end) / 2;
if (mid > end || mid < start) return 0;
if (A[mid] == target) return 1;
if (A[mid] < target) return binarySearch(mid+1, end, target);
if (A[mid] > target) return binarySearch(start, mid-1, target);
return 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
A = new int[N];
for (int i=0; i<N; i++) {
A[i] = sc.nextInt();
}
Arrays.sort(A);
int M = sc.nextInt();
for (int i=0; i<M; i++) {
System.out.println(binarySearch(0, N-1, sc.nextInt()));
}
}
}
이진탐색 방법을 사용하여 구했다.
입력을 A배열에 담고, 오름차순 정렬한 후,
입력받은 값과 A배열의 중간값을 비교하여 더 크면
중간값 이후의 값들과 비교, 작으면 중간값 이전의 값들과 비교해가며
탐색 영역을 반씩 줄여나가는 방법.
첫 번째 코드의 시간 복잡도는 contains메서드를 사용해 O(5*5)정도라고 하면,
이진탐색의 시간복잡도는 O(5*log5) 이기 때문에,
두번째 코드가 시간 초과를 면할 수 있던 것으로 보인다.
개선 사항
import java.util.*;
public class Main {
static int[] A;
public static int binarySearch(int start, int end, int target) {
// while문으로 가독성 UP
while (start <=end) {
int mid = (start + end) / 2;
if (A[mid] == target) return 1;
if (A[mid] < target) start = mid + 1;
else end = mid - 1;
}
return 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
A = new int[N];
for (int i=0; i<N; i++) {
A[i] = sc.nextInt();
}
Arrays.sort(A);
int M = sc.nextInt();
for (int i=0; i<M; i++) {
System.out.println(binarySearch(0, N-1, sc.nextInt()));
}
}
}
- 재귀호출 대신 while 조건문을 사용하여 가독성이 좋아진 듯하다.
- 성능 면에서는 차이가 크게 없을 것으로 보임
Arrays.sort를 사용하면 무조건 비효율적일 것이다 생각했는데,
오히려 contains메서드를 사용한 코드가 더 비효율적일 수 있다는 것을 깨달았던 문제이다.