글 읽기 - Java로 해싱을 이용해서 풀었습니다 시간초과 ㅠㅠㅠ

kssrcn 4년 전 0

체이닝 기법을 이용한 해쉬테이블을 짜서 풀었습니다만 시간초과가 발생합니다 ㅠㅠ 어디가 문제일까요??

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

class LinkedList {
	Node head;
	private class Node {
		Node next;
		int data;
		public Node(int d) {
			next = null;
			data = d;
		}
		public Node getNext() {
			return next;
		}
		public void setNext(Node n) {
			next = n;
		}
		public int getData() {
			return data;
		}
	}
	public void add_first(int d) {
		Node n = new Node(d);
		if(head==null)
			head = n;
		n.setNext(head);
		head = n;
	}
	public boolean search(int d) {
		Node p = head;
		while(p!=null) {
			if(p.getData()==d)
				return true;
			p = p.getNext();
		}
		return false;
	}
}

class HashTable {
	LinkedList[] hash_table;
	int size;
	static final int PN = 23;
	public HashTable() {
		size = 100001;
		hash_table = new LinkedList[100001];
	}
	private int get_key(int d) {
		int key = (d*PN)%size;
		if(key<0)
			return key*-1;
		return key;
	}
	public void add(int d) {
		int key = get_key(d);
		if(hash_table[key]==null) {
			hash_table[key] = new LinkedList();
		}
		hash_table[key].add_first(d);
	}
	public boolean contain(int d) {
		int key = get_key(d);
		if(hash_table[key]==null)
			return false;
		return hash_table[key].search(d);
	}
}



public class Main {
	static int N,M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		HashTable hb = new HashTable();
		st = new StringTokenizer(br.readLine());
		for(int i=0 ; i<N ; i++) {
			hb.add(Integer.parseInt(st.nextToken()));
		}
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0 ; i<M ; i++) {
			int value = Integer.parseInt(st.nextToken());
			if(hb.contain(value)) {
				System.out.println("1");
			}
			else {
				System.out.println("0");
			}
		}
		
	}
	
}

pichulia 4년 전 1

29,30번째 줄이 굉장히 의심스럽습니다. head가 null이면 head에다가 n을 대입하고 있는데, 그 다음에 n의 next에다가 head를 넣고 있습니다. 즉 n의 next는 n 자기 자신이 되버리는거죠... 이거 예제도 안나올고 같은데;;

29/30번째 줄은 지워도 될 것 같습니다.

pichulia 4년 전 1

ㅁ심지어 hash_table 변수는 배열로만 선언해놓고 객체 각각은 초기화를 안해주셨네요...

제가 요즘 사람이 아니라서 잘 모르지만..제가 아는 자바는 저렇게 배열 선언해놓고 for문 돌면서 100001개의 LinkedList 객체를 하나하나 다 초기화 해줘야만 했던걸로 알고있습니다.

으아 심지어 LinkedList class는 객체초기화 함수도 없네요..

kssrcn 4년 전 0

앗.. 29번 if문에 return을 추가안했었군요 추가했습니다! 추가했더니 맞았습니다!

hash_table 초기화는 add 메소드를 호출할때 null이면 생성해주는 방식으로 구현했습니다!

LinkedList 클래스는 초기화 함수가 필요할까요? ㅠㅠ 맴버 변수로 Node head 는 그냥 자동으로 null 처리 되는걸로 알고 있습니다

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

문제

문제

출처

ICPC

Java로 해싱을 이용해서 풀었습니다 시간초과 ㅠㅠㅠ

kssrcn 4년 전 0

pichulia 4년 전 1

pichulia 4년 전 1

kssrcn 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말