백준 (BOJ) 2776 암기왕 java

 

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

2776번: 암기왕

 

 

이분 탐색 / 해시 문제이다.

 

탐색할 때 배열을 사용하지 않는 실수를 범해서 어처구니 없이 많이 틀린 문제

 

이분 탐색 풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
//        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        int N, M;
        int[] arr;

        for(int t=0; t<T; ++t) {
            // 수첩 1
            N = Integer.parseInt(br.readLine());
            arr = new int[N];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; ++i) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(arr);

            // 수첩 2
            M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; ++i) {
                int key = Integer.parseInt(st.nextToken());
                boolean flag = false;

                int l = 0;
                int h = N-1;
                int mid;

                while (l <= h) {
                    mid = (l + h) >> 1;

                    // 탐색한 값이 키 값 보다 작다면,
                    if (arr[mid] < key) {
                        l = mid + 1;
                    }
                    // 크거나 같거나 크다면,
                    else if(arr[mid] > key){
                        h = mid - 1;
                    }
                    else{
                        flag = true;
                        h = mid - 1;
                    }
                }

                if (flag) {
//                    bw.write("1\n");
                    sb.append("1\n");
                }
                else {
//                    bw.write("0\n");
                    sb.append("0\n");
                }

            }
        }
        System.out.print(sb);

//        bw.flush();
//        bw.close();
//        br.close();
    }
}

 

 

 

해시맵 풀이

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T, N, M;
        T = Integer.parseInt(br.readLine());

        for(int t=0; t<T; ++t){
            N = Integer.parseInt(br.readLine());
            // 테케마다 새로운 해시맵을 써야 한다.
            HashMap<Integer, Integer> map = new HashMap<>();

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; ++i){
                map.put(Integer.parseInt(st.nextToken()), 1);
            }

            M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<M; ++i){
                if(map.containsKey(Integer.parseInt(st.nextToken()))){
                    sb.append("1\n");
                }else{
                    sb.append("0\n");
                }
            }
        }

        System.out.print(sb);
    }
}

 

 

 

아래는 시간초과에 의해 탄생한 산출물 C, C++

아주 C++ 답지 않은 코드이다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
	
	int T, N, M;
	int tmp;
	
	scanf("%d", &T);

	for(int t=0; t<T; ++t){
		scanf("%d", &N);
		vector<int> v;
		
		for(int i=0; i<N; ++i){
			scanf("%d", &tmp);
			v.push_back(tmp);
		}
		
		sort(v.begin(), v.end());
		
		int l, h, mid, key;
		bool flag;
	
		scanf("%d", &M);
		for(int i=0; i<M; ++i){
			scanf("%d", &key);
			flag = false;
			
			l = 0, h = N-1;
			
			while (l <= h) {
	            mid = (l + h) >> 1;
	
	            // 탐색한 값이 키 값 보다 작다면,
	            if (v[mid] < key) {
	                l = mid + 1;
	            }
	            // 크거나 같다면,
	            else if(v[mid] > key){
		            h = mid - 1;
		        }
		        else{
		        	flag = true;
		        	h = mid - 1;
				}
		    }
		    
		    if(flag) printf("%d\n", 1); 
	    	else printf("%d\n", 0);
		}
		
	}
	
	return 0;
}