글 읽기 - HashSet이 이분탐색보다 빠른게 아닌가요..?

zaza1994 1년 전 0

안녕하세요.

HashSet을 만들어서 숫자 보유 여부를 판단하여 풀었습니다.

HashSet은 항상 O(1)이라서 가장 빠른줄 알았는데,, 시간초과가 떠서 놀랐습니다.

이분탐색으로 풀면 시간초과가 나오지 않는거 같은데,,, 어째서 그런거죠?

도움 부탁드립니다.

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

public class Main {
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        HashSet<Long> hs = new HashSet<>();
        
		int N = Integer.parseInt(br.readLine());
		
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
        	hs.add(Long.parseLong(st.nextToken()));
        }
        
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        String ret = "";
        for(int i = 0; i < M; i++) {
        	long ref = Long.parseLong(st.nextToken());
        	if(hs.contains(ref)) ret += "1 ";
        	else ret += "0 ";
        }
        
		bw.write(ret + "\n");
        bw.flush();
        bw.close();
	}
	

}

stylecoke 1년 전 1

제 생각에는 HashSet보다는 String +연산 때문에 시간초과가 발생하는 것 같습니다.

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        HashSet<Long> hs = new HashSet<>();
        
		int N = Integer.parseInt(br.readLine());
		
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
        	hs.add(Long.parseLong(st.nextToken()));
        }
        
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < M; i++) {
        	long ref = Long.parseLong(st.nextToken());
        	if(hs.contains(ref)) ret.append("1 ");
        	else ret.append("0 ");
        }
        
		bw.write(ret.toString());
        bw.flush();
        bw.close();
	}

zaza1994 1년 전 0

덕분에 해결했습니다.

String 연산이 생각보다 오래걸리네요

StringBuilder를 쓰는 습관을 길러야겠습니다.

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

HashSet이 이분탐색보다 빠른게 아닌가요..?

zaza1994 1년 전 0

stylecoke 1년 전 1

zaza1994 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말