SISS/HackerRank(C)
[Search] Pairs
3190024
2020. 10. 3. 23:44
int형 타입으로 이루어진 배열 arr이 주어지는데, 배열의 숫자들 중에서 차가 k인 숫자 짝의 개수를 구해야 한다.
5 2
1 5 3 4 2
가 주어진다면 첫번째 줄의 첫번째 숫자 5는 숫자 배열의 크기이고, 첫번째 줄의 두번째 숫자 2는 k를 의미한다.
두번째 줄은 배열에 들어가는 숫자들이다.
여기서 차가 2가 되는 조합은 (3,1), (5,3),(4,2)로 모두 3가지이다.
맨 처음에 그저 정렬을 안하고
for(int i = 0, i < arr_count; i++){
for(int j = i+1; j<arr_count;j++{
if((k == arr[i]-arr[j]) || (k == arr[j]-arr[i])){
count++;
break;
}
}
}
이런 식으로 했다가 타임 아웃에 걸렸다.
이것 말고도 정렬을 안하고 여러 시도를 해 보았지만 모두 타임 아웃이었다.
결국 정렬을 하기로 했다. 선택정렬과 삽입정렬을 모두 시도해 봤지만 역시 타임 아웃에 걸렸다. 마지막으로 퀵 정렬로 시도했는데, 이전보다는 타임아웃에 걸리는 test case가 적었다. 퀵 정렬은 그대로 두고, 탐색을 하는 코드에서 두 개의 인덱스 변수(?)를 이용했다.
