글 읽기 - java hashmap으로 하면 왜 시간초과가 발생하나요?

pjy1368 3년 전 0

put과 containsKey 모두 시간복잡도가 O(1)인 것으로 알고 있는데 이 문제에서 시간초과가 나는 이유가 궁금합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());

		long[][] arr = new long[N][4];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) {
				arr[i][j] = Long.parseLong(st.nextToken());
			}
		}

		long[] AB = new long[N * N];
		Map<Long, Long> map = new HashMap<>();
		int idx = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				AB[idx++] = arr[i][0] + arr[j][1];
				long sum = arr[i][2] + arr[j][3];

				if (map.containsKey(sum)) {
					map.put(sum, map.get(sum) + 1);
				} else {
					map.put(sum, 1L);
				}
			}
		}

		long ans = 0;
		for (int i = 0; i < AB.length; i++) {
			long key = -AB[i];

			if (map.containsKey(key)) {
				ans += map.get(key);
			}
		}

		bw.write(ans + "\n");
		bw.flush();
		bw.close();
		br.close();

	}
}

herdson 3년 전 0

해시테이블을 잘 저격하면 시간복잡도가 O(n)이 걸리게 만들 수 있습니다.

pjy1368 3년 전 0

어떤 조건에서 hashmap의 시간복잡도가 O(N)이 되는 건가요?

herdson 3년 전 2

매번 수를 넣을때마다 해시 충돌을 일으키게 하면 됩니다.
https://www.secmem.org/blog/20...

ㄴ 글 후반부에 c++ unordered_map 에서 시간복잡도가 O(n)이 되는 수열을 생성하는 코드가 있습니다.
https://codeforces.com/blog/en...
ㄴc++ unordered_map의 저격을 방지하는 방법. 이 문제에서는 통하지 않았습니다.

pjy1368 3년 전 0

그렇다면.. 어떤 경우에는 해쉬맵을 쓰면 안되는걸까요? 단순히 해쉬맵에 저장되는 데이터가 한 1000만이상이 넘어가면 안 쓰려고해야하는걸까요?

이 문제에 경우, 수를 넣을 때마다 해쉬 충돌을 야기할 수도 있겠구나싶은데, 다른 문제를 풀 때에도 해쉬 충돌을 어떻게 고려해야할지 궁금합니다.

herdson 3년 전 0

코드포스같은 커뮤니티에서는 되도록 트리맵으로 처리가 가능한 범위까지만 맵/셋 사용을 고려하고 수가 너무 많이 주어진다 싶으면 다른 방법을 찾으라고 권하고 있습니다.

pjy1368 3년 전 0

트리맵이 시간복잡도가 O(logN)으로 알고있는데, 연산 과정에서 어떠한 시간복잡도와 트리맵의 시간복잡도를 계산하였을 때 시간 안에 처리가 가능하지 않다면 맵 자체를 쓰지 말라는 말씀이신가요??

herdson 3년 전 2

예 그렇습니다. 그렇게 많은 데이터라면 분명 해쉬를 저격하는 데이터도 포함이 되었을거라는 거죠.

pjy1368 3년 전 0

친절한 답변 감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

java hashmap으로 하면 왜 시간초과가 발생하나요?

pjy1368 3년 전 0

herdson 3년 전 0

pjy1368 3년 전 0

herdson 3년 전 2

pjy1368 3년 전 0

herdson 3년 전 0

pjy1368 3년 전 0

herdson 3년 전 2

pjy1368 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말