[백준] 10815 : 숫자카드

이진탐색을  사용하고 싶었는데 정확한 구현 방법이 기억이 안나서 찾아보고 구현함.

반복형과 재귀형 둘 다 사용해봤는데 메모리와 시간에 눈에 띄게 큰 차이는 없었다.

 

2등코드

메모리 : 41008 KB

시간 : 360 ms

코드길이 : 1929 B

 

내 코드

메모리 : 108760 KB

시간 : 1268 ms

코드길이 : 1234 B

>> 상위권 코드와의 차이가 너무 큼.. 

 

[2등 코드]

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;

public class Main {
    static class Reader {
        private final int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

    }

    public static void main(String[] args) throws IOException {
        Reader r = new Reader();
        int n = r.nextInt();
        boolean[] check = new boolean[20_000_001];
        for (int i = 0; i < n; i++) {
            check[r.nextInt() + 10_000_000] = true;
        }
        int m = r.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            if (check[r.nextInt() + 10_000_000]) {
                sb.append('1').append(' ');
            } else {
                sb.append('0').append(' ');
            }
        }
        System.out.print(sb);
    }
}

 

[내 코드]

 

1. 반복형

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {
	public static int[] numCard;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		numCard = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int n = 0; n < N; n++) {
			numCard[n] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(numCard); //오름차순 배열
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int m = 0; m < M; m++) {
			sb.append(binarySearch(Integer.parseInt(st.nextToken()), 0, N-1)).append(" ");
		}
		
		System.out.println(sb);
	}
	
	static int binarySearch(int num, int low, int high) {
		int mid;
		while(low <= high) {
			mid = (low + high) / 2;
			
			if(num == numCard[mid])
				return 1;
			else if(num > numCard[mid])
				low = mid + 1;
			else if(num < numCard[mid])
				high = mid - 1;
		}
		return 0;
	}

}

2. 재귀형

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {
	public static int[] numCard;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		numCard = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int n = 0; n < N; n++) {
			numCard[n] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(numCard); //오름차순 배열
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int m = 0; m < M; m++) {
			sb.append(binarySearch(Integer.parseInt(st.nextToken()), 0, N-1)).append(" ");
		}
		
		System.out.println(sb);
	}
	
	static int binarySearch(int num, int low, int high) {
		int mid;
		if(low <= high) {
			mid = (low + high) / 2;
			if(num == numCard[mid])
				return 1;
			else if(num < numCard[mid]) 
				return binarySearch(num, low, mid - 1);
			else if(num > numCard[mid])
				return binarySearch(num, mid + 1, high);
		}
		return 0;
	}

}