│문제
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
│Python풀이
N=int(input())
arr_N=list(map(int,input().split()))
arr_N.sort()
M=int(input())
arr_M=list(map(int,input().split()))
def binarySearch(arr,target):
left=0
right=N-1
while left<=right:
mid =(left+right)//2
if arr[mid]== target:
return True
elif arr[mid]>target:
right=mid-1
else:
left=mid+1
return False
for i in range(M):
if binarySearch(arr_N,arr_M[i]):
print(1)
else:
print(0)
│설명 (Python)
첫번째 풀이에서는 파이썬의 장점인 간단한 문장으로 아래와 같이 풀이 하였다.
N=int(input())
arr_N=list(map(int,input().split()))
M=int(input())
arr_M=list(map(int,input().split()))
for i in range(M):
if arr_M[i] in arr_N:
print(1)
else:
print(0)
하지만 문제에 (모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. )와 같은 조건이 있듯이 당연하게 시간초과 문제가 발생하였다.
keypoint 1- python의 'in'연산자는 시간복잡도가 O(n)이다.
if문 같은 조건문에서 많이 사용되는 in 연산자는 위에서 arr_N안에 arr_M[i]의 값이 원소로 존재하는지 확인한다.
하지만 'in'연산자는 확인할 때 모든 원소를 처음부터 쭉 검사하므로 시간 복잡도가 O(n)이다.
수 찾기와 같이 범위가 매우 큰 문제는 시간 복잡도를 최소화 하여 시간초과가 발생하지 않는것에 중점을 두어야 한다.
시간 복잡도를 줄이기 위해 이분탐색(Binary Search)를 활용 하였다.
def binarySearch(arr,target):
left=0
right=N-1
while left<=right:
mid =(left+right)//2
if arr[mid]== target:
return True
elif arr[mid]>target:
right=mid-1
else:
left=mid+1
return False
bool형을 리턴하여 아래와 같이 if문을 간략하게 작성하였다.
if binarySearch(arr_N,arr_M[i]):
│C언어 풀이
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b)
{
int num1 = *(int*)a;
int num2 = *(int*)b;
if (num1 < num2)
return -1;
if (num1 > num2)
return 1;
return 0;
}
int binsearch(int data[], int n, int key) {
int low, high;
int mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (key == data[mid]) {
return 1;
}
else if (key < data[mid]) {
high = mid - 1;
}
else if (key > data[mid]) {
low = mid + 1;
}
}
return 0;
}
int main(void) {
int N = 0;
int M = 0;
int A[100000];
int target[100000];
int result[100000];
int num = 0;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &num);
A[i] = num;
}
qsort(A,N,sizeof(int),compare);
scanf("%d", &M);
for (int i = 0; i < M; i++) {
scanf("%d", &num);
target[i] = num;
result[i] = binsearch(A, N, num);
}
for (int i = 0; i < M; i++)printf("%d\n", result[i]);
return 0;
}
│설명 ( C언어)
void sort(int* tmparr,int size) {
int temp = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < (size - 1) - i; j++) {
if (tmparr[j] > tmparr[j + 1]) {
temp = tmparr[j];
tmparr[j] = tmparr[j + 1];
tmparr[j + 1] = temp;
}
}
}
}
첫 풀이에서 c언어는 파이썬과 다르게 sort()와 같은 편리한 함수가 없으므로 위와 같이 버블정렬을 사용하였는데 당연하게도 시간초과 문제가 발생했다. 위 코드와 같은 경우 이중 for문이므로 시간 복잡도가 O(n^2)이라는 사실을 알 수 있다.
시간 복잡도가 보통 제일 적은 정렬을 꼽자면 퀵정렬과 병합정렬이 있는데 퀵정렬과 이분탐색을 선택하여 문제 풀이를 진행하였다.
keypoint 1- c언어에서 <stdlib.h> 라이브러리에서 아래와 같이 qsort함수가 정의되어 있다.
void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *));
void *base: 정렬하고자 하는배열
size_t nel:배열의 사이즈
size_t width : 배열에서 원소의 사이즈 ex)sizeof(int),sizeof(float)
int (*compare)(const void *, const void *): 비교함수 / 비교함수는 아래와 같이 작성할 수 있다.
int compare(const void* a, const void* b)
{
int num1 = *(int*)a;
int num2 = *(int*)b;
if (num1 < num2)
return -1;
if (num1 > num2)
return 1;
return 0;
}
각 if문 아래의 숫자인 -1과 1을 바꿔보면 오름차순과 내림차순을 조절할 수 있다.
정리하면 void qsort(정렬하고자 하는 배열, 사이즈, 배열에서 원소의 사이즈 ,비교함수) 라 할 수 있다.
풀이에서qsort(A,N,sizeof(int),compare); 로 배열을 정렬한 후
int binsearch(int data[], int n, int key) {
int low, high;
int mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (key == data[mid]) {
return 1;
}
else if (key < data[mid]) {
high = mid - 1;
}
else if (key > data[mid]) {
low = mid + 1;
}
}
return 0;
}
이분탐색을 통해 비교를하여 풀이하였다.
1920번 수 찾기문제는 보기에는 매우 간단하지만 시간초과를 통해 어떻게 해결해 나가야 할지 생각하는 부분에서 배울 점이 많은 좋은 문제이다.
