1920번 수 찾기
코딩테스트 : 1920번 수 찾기
| 1 초 | 128 MB | 313352 | 101050 | 66425 | 30.714% |
문제
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을 출력한다.
using System.Linq;
using System.Collections.Generic;
using System.Text;
public class BackJoon
{
// 정렬하는데는 많이 안드나.. ?
public static void Main()
{
int N = int.Parse(Console.ReadLine());
List<int> numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
int M = int.Parse(Console.ReadLine());
int[] targetNumbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
StringBuilder sb = new StringBuilder();
numbers.Sort();
for (int i = 0; i < M; i++)
{
sb.AppendLine(binarySearch(numbers,0,numbers.Count -1 , targetNumbers[i]).ToString());
}
Console.WriteLine(sb);
}
public static int binarySearch(List<int> numbers, int start, int end, int target)
{
if (start > end) return 0;
int mid = (start + end) / 2;
if (numbers[mid] == target) return 1;
if (target > numbers[start] && target < numbers[mid])
{
return binarySearch(numbers, start, mid -1 , target);
}
else
{
return binarySearch(numbers, mid + 1, end, target);
}
}
}
처음에 이렇게 했다가 다음 입력에서 1을 제대로 감지하지 못했다.
5
4 1 5 2 3
5
1 3 7 9 5
그 이유는 조건을 제대로 설정하지 않았기 때문이다.
정렬을 하면 1은 첫 번째 인덱스이기 때문에 1이 들어와서 비교를 할 때 false값이 나오게 되고, 잘못된 방향으로 이동해
0이 나오게 되는 것이다.
이분 탐색에서는 굳이 이런 두 가지로 탐색을 할 필요 없이, 그냥 중간값을 기준으로 좌 우를 나눠주는 것이 편하다.
두 가지 의문점을 갖고 문제에서 고민했다.
1. 짝수 홀수는 따로 구분해줄 필요가 없는 것인가 ?
다양한 문제들에서 짝수/홀수의 경우를 나눠서 푸는 문제가 많았기에 고민했다.
다만 C#에서 /로 나눗셈을 한다면 결국 몫만 취해 오는 것이고, 그 몫을 기준으로 나뉘는 것이고, 나뉜 것들에서 전부 다 탐색을 하면 상관없는 것이다. ( 짝수의 경우 mid를 제외하면 홀수가 되므로 정확히 절반으로 나뉘지 않아도, 모든 index들이 검사되는 것이므로 상관 없다 )
2. 중간에 binarySearch에서 조건에 mid - 1 , mid + 1 을 하지 않았을 때의 오류
처음에는 그냥 mid를 둘 다 검사해도 많은 리소스가 들지 않을 것이라고 판단하고 mid, mid를 사용했다.
다만 이 경우 StackOverFlow가 발생했다. 그 이유를 찾아보니 다음과 같은 예시에서, 계속해서 중복 호출이 발생하는 문제였다.
예를 들어, start = 3 / end = 4일 때 mid는 3이되고 다음 재귀 호출도 start = 3, end = 4가 된다.
같은 mid가 반복되는 것이므로 무한루프가 발생해 StackOverFlow가 발생했다.
즉, 이미 비교한 midIndex는 제외해 주어야 무한루프가 발생하지 않는다 .