na982   4년 전

아이디어는 123 이라는 번호가 들어오면,

1이 기존에 저정되었는지 확인하고,

12 가 기존에 저장되어있는지 확인하고,

123 이 기존에 저장되었는지 확인하고,

3개다 저장이 안되어있으면 123을 저장하고, 다음번 전화번호를 입력받고

기존에 저장되어있었다면 앞으로 체크하지 않고 남은 입력만 받은후에 NO를 출력하는것인데;


코드와 아이디어 모두 비는 곳을 못찾겠는데 정답이 안나오네요.ㅜ

chogahui05   4년 전

해쉬값 충돌이 나지 않나 점검해 보세요.

다른 데이터가 같은 키를 가지지 않는지를 점검하시는 게 우선인 듯 싶네요.

현실적으로 엄청나게 많은 문자열이 들어오는데 충돌이 나지 않게 짜시는 건 매우 어렵습니다.


충돌이 나는 경우에는 색인들 중에서 비어 있는 곳에 넣는 방식을 쓰거나 (Open Addressing)

혹은 기존 주소에 새로 노드를 추가하는 방식 (Seperate Chaining)이 있는데요.


jre 8 이상의 HashMap은

후자의 방법으로, Red Black Tree로 구현합니다.

na982   4년 전

2

123

12345

의경우는 일관성이 없는 경우이고,


2

12345

123

의 경우도 일관성이 없는 경우 입니다.

chogahui05   4년 전

알고리즘 자체는 맞아요.

단 "Hash 값이 충돌나지 않는 전제" 하에서요.

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