[BaekJoon]#1654 수 찾기

문제를 해석해보자면, N과 M은 배열의 크기이다. 그리고 두번째 입력한 각각의 원소가 첫번째 배열 A안에 존재하면 1, 존재하지 않으면 0 을 반환하는 문제이다.
재밌다. 수학문제 푸는 것 같아!

이진탐색 알고리즘은 외웠고 다 쓸 줄 아는데 .. 혼자 쭉쭉 써내려갈 실력은 없어서 아래 블로그를 참조했다.

참조블로그

import java.util.Scanner;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int Arr[] = new int[N];
        
        for(int i=0; i<N ; i++){
            Arr[i] = in.nextInt();
        }
        
        Arrays.sort(Arr);
        
        int M = in.nextInt();
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i < M ; i++){
            if(binarySearch(Arr, in.nextInt())>=0){
                sb.append(1).append('\n');    
            }
            else{
                sb.append(0).append('\n');
            }          
        }
        System.out.println(sb);
    }
    public static int binarySearch(int arr[], int key){
        int low =0 ;
        int high = arr.length-1; 
        
        while(low<=high){
            int mid = ( low + high )/2;
            
            if(key<arr[mid]){
                high = mid-1;               
            }
            else if(key>arr[mid]){
                low = mid+1;
            }else {
                return mid;
            }
            
        }
        return -1;
    }
}

Main

• 우선, Main 함수를 뜯어서 살펴봅시다.
• 이 코드에서는 StringBuilder를 사용해서 수를 입력받았습니다.
• StringBuilder는 보통 for문과 같은 반복문과 함께 사용되며 append메서드를 통해 문자열을 추가합니다.

StringBuilder를 사용하는 이유?

• StringBuilder는 가변객체로, 문자열을 추가하거나 수정할 때 새로운 객체를 생성하지 않고, 내부의 버퍼를 변경합니다.

• 그렇기 때문에 성능과 메모리 측면에서 효율적입니다.

• 특히, 문자열 연결 연산이 빈번하게 일어나는 경우, StringBuilder를 사용하여 속도를 향상시킬 수 있습니다.

• 사용자의 입력을 바로 Stringbuilder 객체 안에 넣어주려면 다음과 같이 코드를 작성하면 됩니다.

 StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            String line = in.nextLine();
            sb.append(line).append('\n'); // 각 줄을 추가하고 개행 문자 추가
        }
        

---

• 이 코드에서는 사용자의 입력을 저장하지 않고, 입력받은 값을 바로 binarySearch() 함수로 넘겨줍니다. binarySearch() 함수의 반환값에 따라, 사용자가 입력한 수가 배열 Arr에 존재하는지 여부를 판단합니다.
• 이 결과를 StringBuilder 객체인 sb에 append 메서드를 사용하여 추가합니다.

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int Arr[] = new int[N];
        
        for(int i=0; i<N ; i++){
            Arr[i] = in.nextInt();
        } 
        
        Arrays.sort(Arr); // 배열 A 생성 과정
        
        int M = in.nextInt(); // 배열 B(비교대상) 크기 입력받기
        
        StringBuilder sb = new StringBuilder(); // 
        
        for(int i=0;i < M ; i++){
            if(binarySearch(Arr, in.nextInt())>=0){
                sb.append(1).append('\n');    
            }
            else{
                sb.append(0).append('\n');
            }          
        }
        System.out.println(sb);
    }

---

binarySearch()

• binarySearch 함수를 살펴봅시다. 코드는 아래와 같습니다.

public static int binarySearch(int arr[], int key){
        int low =0 ;
        int high = arr.length-1; 
        
        while(low<=high){
            int mid = ( low + high )/2;
            
            if(key<arr[mid]){
                high = mid-1;               
            }
            else if(key>arr[mid]){
                low = mid+1;
            }else {
                return mid;
            }
            
        }
        return -1;
    }

• binarySearch 함수는 배열 A에 해당하는 int arr[]과, key를 매개변수로 받고 있습니다.
• 매개변수만 달리 받을 뿐, 나머지는 기존 binarySearch 코드와 동일합니다.