[Silver V/JAVA] 10815 숫자카드

https://www.acmicpc.net/problem/10815

 

 

• 이진탐색을 사용하지 않고 배열을 일일이 비교하면 시간초과가 뜬다.
• 이진탐색(Binary Search)를 사용해서 풀어야 하는 문제 (https://marginata.tistory.com/150)
• 풀이 1은 System.out.print() 를 이용하여 일일이 출력을 했고, 풀이 2는 StringBuilder를 사용하여 출력을 했다. 성능면에서 StringBuilder를 사용하는 것이 훨씬 더 빠르다.

 

풀이 1

 

import java.io.*;
import java.util.*;

public class Main{
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //상근이가 가진 카드
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine(), " ");
        
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        //이진탐색을 위한 정렬
        Arrays.sort(arr);
        
        //비교할 카드
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        
        for(int i=0; i<M; i++){
            int result = binarySearch(Integer.parseInt(st.nextToken()));
            if(result != -1) System.out.print(1 + " ");
            else System.out.print(0 + " ");
                                      
        }
    }
    
    //이진탐색
    private static int binarySearch(int target){
        int left = 0;
        int right = arr.length-1;
        int mid;
        
        while(left <= right){
            mid = (left+right)/2;
            if(arr[mid] < target) left = mid+1;
            else if(arr[mid] > target) right = mid-1;
            else return mid;
        }
        return -1;
    }
}

 

 

풀이 2

 

import java.io.*;
import java.util.*;

public class Main{
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //상근이가 가진 카드
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine(), " ");
        
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        //이진탐색을 위한 정렬
        Arrays.sort(arr);
        
        //비교할 카드
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        
        //StringBuilder로 출력
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<M; i++){
            int result = binarySearch(Integer.parseInt(st.nextToken()));
            sb.append(result).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
    
    //이진탐색
    private static int binarySearch(int target){
        int left = 0;
        int right = arr.length-1;
        int mid;
        
        while(left <= right){
            mid = (left+right)/2;
            if(arr[mid] == target) return 1; //값이 있음
            else if(arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return 0; //값이 없음
    }
}

 

 

위가 StringBuilder를 이용한 결과. 메모리와 시간이 더 적게 드는 것을 확인할 수 있다