글 읽기 - [시간초과] map을 이용한 구현이 가능한지 질문드립니다

smgod 4년 전 0

안녕하세요 다른 코드들 참고해서 lower bound . upper bound 를 두고 이진탐색을 해서 찾는건 이해했습니다.

저는 처음에 이문제를 map 을 통해서 접근하려고 했는데 왜 Map을 사용하면 안되는지 궁금합니다.

unordered map사용시 O(1) 이면 삽입과 서치가 가능하다고 찾았습니다.

A + B를 해서 나오는 경우의 수를 map ab로 매핑하고

C+ D 를 해서 나오는 겨우의 수를 mab cd로 매핑하였습니다.

* 다만 해쉬 collison 떄문에 느려질 수 있다고 봤는데 5000* 5000 = 25,000,000 2천 5백만개의 데이터에서도 해쉬 충돌이 발생하나요 ?

또 만약 제 코드에서 속도를 추가적으로 감속시킬수 있는 방안이 있다며 알려주시면 감사하겠습니다 ㅜㅜ

혹시또 Map으로 짜신분이 있다면 한수 알려주세요

* 그리고 추가적으로 이진 탐색문제(포켓몬문제 , 등등 위에 문제) 를 Map 을 이용해서 많이 풀었는데

Map 을 이용했을 경우와 이진탐색을 이용했을 경우 속도차이가 얼마나 나는지도 알고싶습니다.

감사합니다 :)

#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;
int arrA[4001] = { 0, };
int arrB[4001] = { 0, };
int arrC[4001] = { 0, };
int arrD[4001] = { 0, };
unordered_map<int, int>ab;
unordered_map<int, int>cd;
int main(void)
{
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
	{
		scanf("%d %d %d %d", &arrA[i], &arrB[i], &arrC[i], &arrD[i] );
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int k = arrA[i] + arrB[j];
			int t = arrC[i] + arrD[j];
			ab[k] = 1 + ab[k];
			cd[t] = 1+ab[t];
		}
	}
	unsigned long long int sum = 0;
	for (auto it = ab.begin(); it != ab.end(); it++)
	{
		sum = sum + ab[it->first] * cd[it->first * (-1)];
	}
	printf("%llu", sum);
	return 0;
}

bupjae 4년 전 0

저는 다른 언어 (golang) 을 이용합니다만, map 을 이용해서 풀었습니다. (제출번호 7989400)

golang 의 map 은 개념적으로 C++의 unordered_map 과 비슷한 자료구조 라고 생각하시면 됩니다.

다만, 시간이 빡빡하게 나오게 되었습니다. 데이터에 따라서는 제한 시간을 초과할 지도 모르겠네요.

package main

import (
	"bufio"
	"fmt"
	"os"
)

var in = bufio.NewScanner(os.Stdin)

func nextInt() int32 {
	in.Scan()
	var r, f int32
	f = 1
	for _, c := range in.Bytes() {
		if c == '-' {
			f = -1
			continue
		}
		r *= 10
		r += int32(c - '0')
	}
	return r * f
}

func main() {
	in.Split(bufio.ScanWords)
	n := nextInt()
	a, b, c, d := make([]int32, n), make([]int32, n), make([]int32, n), make([]int32, n)
	ab, cd := make(map[int32]int), make(map[int32]int)
	for n > 0 {
		n--
		a[n], b[n], c[n], d[n] = nextInt(), nextInt(), nextInt(), nextInt()
	}
	for _, a := range a {
		for _, b := range b {
			ab[a+b]++
		}
	}
	for _, c := range c {
		for _, d := range d {
			cd[c+d]++
		}
	}
	r := 0
	for k, v := range ab {
		r += v * cd[-k]
	}
	fmt.Println(r)
}

eirc8260 4년 전 0

저도 unordered_map으로 구현했는데 시간초과나네요

unordered_map.rehash() 쓰면 collision 줄어들지않을까해서 해봤는데 안되네여 ㄷㄷ

indioindio 4년 전 0

저는 python(정확히는 pypy)를 이용하였는데, ab cd의 맵을 만들지 않고 cd에 대해서만 map을 만들고, ab 가능한 합들에 대해서 해당하는 짝이 있는지를 cd에서 확인하였습니다.

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

문제

문제

출처

ICPC

[시간초과] map을 이용한 구현이 가능한지 질문드립니다

smgod 4년 전 0

bupjae 4년 전 0

eirc8260 4년 전 0

indioindio 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말