10815번: 숫자 카드(Java)

 

 

 

 

숫자가 너무 커서 이진 탐색을 사용해야 시간제한 내에 풀 수 있을 것 같았다.

우선 상근이의 카드를 입력받은 후 정렬해야 한다(이진 탐색은 정렬이 조건이므로)

이진 탐색에 필요한 변수 몇 개를 포함해 선언하고 입력을 받았다.

 

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();//상근이의 카드 수
int[] card = new int[n];//상근이의 카드
int m;//찾을 카드의 수
int find;//찾을 카드
int low;//최소 index
int high;//최대 index
int mid;//중앙 index
int[] result;//결과


//상근이의 카드를 입력받는다
for(int i = 0; i<n; i++)
{
    card[i] = scanner.nextInt();
}

//정렬(Binary Search 의 조건은 정렬이다)
Arrays.sort(card);

 

 

 

 

 

 이제 찾을 카드를 입력받음과 동시에 이진 탐색으로 찾고 찾았다면 result에 1을 넣으면 된다. Java에서는 정수 배열을 생성하고 값을 따로 할당하지 않으면 모든 값이 0으로 초기화되므로 찾은 카드에만 1을 넣으면 된다. 

 

//Binary Search
for(int i = 0; i<m; i++)
{
    find = scanner.nextInt();
    low = 0;
    high = n - 1;
    while(low <= high)
    {
        mid = (low + high) / 2;
        if(card[mid] == find)
        {
            result[i] = 1;
            break;
        }
        else if(card[mid] < find)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
}

 

 

 

 

출력하면 끝

for(int i = 0; i<m; i++)
{
    System.out.print(result[i] + " ");
}

 

 

 

 

 

 

 

<전체 코드>

import java.util.*;
    
public class Main
{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//상근이의 카드 수
        int[] card = new int[n];//상근이의 카드
        int m;//찾을 카드의 수
        int find;//찾을 카드
        int low;//최소 index
        int high;//최대 index
        int mid;//중앙 index
        int[] result;//결과
        //상근이의 카드를 입력받는다
        for(int i = 0; i<n; i++)
        {
            card[i] = scanner.nextInt();
        }
        //정렬(Binary Search 의 조건은 정렬이다)
        Arrays.sort(card);
        m = scanner.nextInt();
        result = new int[m];
        //Binary Search
        for(int i = 0; i<m; i++)
        {
            find = scanner.nextInt();
            low = 0;
            high = n - 1;
            while(low <= high)
            {
                mid = (low + high) / 2;
                if(card[mid] == find)
                {
                    result[i] = 1;
                    break;
                }
                else if(card[mid] < find)
                {
                    low = mid + 1;
                }
                else
                {
                    high = mid - 1;
                }
            }
        }
        for(int i = 0; i<m; i++)
        {
            System.out.print(result[i] + " ");
        }
    }
}