글 읽기 - java 시간초과 hash map 기능 없이 못 푸는 문제인가요?

idc06012 2년 전 0

풀이 방법 보면 hash map이라는 메소드를 다들 활용하셨던데

다른 문제에서 ArrayList 기능 활용한거는 그냥 배열로 해서 다 풀렸는데

이 문제는 map 메소드를 대체할 수 있는 방법이 뭔지 모르겠습니다

원래 배열과 번호를 부여한 배열끼리 비교할 때 for문 속에 for문으로 if로 찾는데 이것땜에 시간초과 나는 것 같아서요

hash map이라는 메소드 혹은 이미 java에서 제공하는 메소드를 사용안하고는 못푸나요?

djm03178 2년 전 0

그 메소드에서 구현하고 있는 것을 직접 구현해보는 것도 방법입니다.

slah007 2년 전 2

병합 정렬, 힙 정렬 등 O(n lg n)의 정렬을 수행하고 나면 같은 원소를 O(n)만에 뽑아낼 수 있으므로(다음 원소와 다른 것만 뽑는다던지) 다시 각각의 원소가 뽑아낸 배열에서 몇 번째인지 이진 탐색으로 찾으면 압축을 수행할 수 있습니다.

시간복잡도는 같지만 map을 사용하는 것보다 정렬과 이진 탐색을 사용하는 쪽이 최악의 경우 상수 계수 측면에서 훨씬 빠릅니다. 대신 최악의 경우를 고려하지 않고 unordered_map을 쓰면 평균 시간은 더 빠를 수도 있고 map쪽이 구현이 약간 더 짧으므로 장단점이 있습니다.

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

문제

문제

출처

ICPC

java 시간초과 hash map 기능 없이 못 푸는 문제인가요?

idc06012 2년 전 0

djm03178 2년 전 0

slah007 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말