[BaekJoon/C#] 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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

 

출력 

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제

입력:

5
4 1 5 2 3
5
1 3 7 9 5

출력: 

1
1
0
0
1

 

 

코드1 - while문

using System; 
using System.Text;

class Program 
{
    static void Main(string[] args) 
    { 
        StringBuilder sb = new StringBuilder();
        int totalC = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Trim().Split(); 
        int[] criteria = new int[str.Length];
        int totalS = int.Parse(Console.ReadLine());
        string[] search = Console.ReadLine().Trim().Split();

        for(int i=0; i<str.Length; i++)
        {
            criteria[i] = int.Parse(str[i]);
        }

        Array.Sort(criteria);
        
        for(int i=0; i<totalS; i++)
        {
            int low = 0;
            int high = criteria.Length-1;
            bool found = false;
            
            while(low<=high && !found) 
            {
                int mid = (low+high)/2;

                if(criteria[mid] == int.Parse(search[i])) found = true;
                else if(criteria[mid] > int.Parse(search[i])) high = mid-1;
                else low = mid+1;
            }
            sb.Append(found?"1\n":"0\n"); 
        }
        Console.WriteLine(sb.ToString()); 
    }
}

 

코드2 - 재귀함수

using System; 
using System.Text;

class Program
{ 
    static void Main(string[] args) 
    { 
        StringBuilder sb = new StringBuilder();
        int totalC = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Trim().Split(); 
        int[] criteria = new int[str.Length];
        int totalS = int.Parse(Console.ReadLine());
        string[] search = Console.ReadLine().Trim().Split();

        for(int i=0; i<str.Length; i++)
        {
            criteria[i] = int.Parse(str[i]);
        }

        Array.Sort(criteria);
        
        for(int i=0; i<totalS; i++)
        {
            sb.Append(BinarySearch(criteria, int.Parse(search[i]), 0, criteria.Length-1)? "1\n":"0\n"); 
        }
        
        Console.WriteLine(sb.ToString()); 
    } 

    static bool BinarySearch(int[] criteria, int element, int low, int high) 
    {
        if(low>high) return false;
        
        int mid = (low+high)/2;
        if(criteria[mid] == element) return true;
        else if(criteria[mid] > element) return BinarySearch(criteria, element, low, mid-1);
        else return BinarySearch(criteria, element, mid+1, high);
    }
}

 

 

참고

이 문제를 풀 때 처음에는 단순히 IndexOf를 사용했지만 '시간 초과'로 인해 다른 방법을 사용해야 했다. 

그래서 이진탐색을 이용해서 코드를 작성했더니 '시간 초과'는 아니었지만 '틀렸습니다'가 나왔다.

VSCode에서 돌려볼 땐 결과에 문제가 없었는데 왜 틀렸는지 알 수가 없었다. 

그래서 반례를 찾아보다가 백준 질문글에서 발견한 다른 사람의 반례를 넣어봤더니 출력 결과가 이상했다.

반례)
7
1234567890 12345 987654321 1357924680 -1234543210 -999999999 2147483647
7
1111111111 1234567890 987654321 0 12345 -999999999 -2122222222

정답)
0
1
1
0
1
1
0

출력)
0
1
0
0
1
1
0

 

왜 그런가 원인을 찾아봤더니 처음에 코드 짤 때 criteria를 int가 아닌 string 배열로 해서 Sort했더니 

string[] criteria = Console.ReadLine().Trim().Split(); 

Array.Sort(criteria);

 

[-1234543210]  [-999999999]  [12345]  [1234567890]  [1357924680]  [2147483647]  [987654321]

위 결과처럼 정렬됐다...

숫자의 첫 번째만 보고 정렬되어서 이상한 결과가 나왔던 것이다. 

그래서 입력받은 string을 str에 먼저 저장하고 다시 criteria에 int로 변환해서 저장했더니 해결됐다.

string[] str = Console.ReadLine().Trim().Split(); 
int[] criteria = new int[str.Length];
      
for(int i=0; i<str.Length; i++)
{
	criteria[i] = int.Parse(str[i]);
}

Array.Sort(criteria);

 

 

(추가)

코드3 - List<T>.BinarySearch 메소드

using System; 
using System.Text;
using System.Collections.Generic;

class Program
{ 
    static void Main(string[] args) 
    { 
        StringBuilder sb = new StringBuilder();
        int totalC = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Trim().Split(); 
        List<int> criteria = new List<int>();
        int totalS = int.Parse(Console.ReadLine());
        string[] search = Console.ReadLine().Trim().Split();

        for(int i=0; i<str.Length; i++)
        {
            criteria.Add(int.Parse(str[i]));
        }

        criteria.Sort();
        
        for(int i=0; i<totalS; i++)
        {
            int index = criteria.BinarySearch(int.Parse(search[i]));
            sb.Append(index < 0? "0\n":"1\n"); 
        }
        
        Console.WriteLine(sb.ToString()); 
    } 
}