HashMap 검색 결과

해당 글 10건
key multiple value 처리를 물어본 가희와 파일탐색기 2 문제를 풀어봅시다.

저는 모 대회에서 3개 이상 푼 분을 절반 이상으로 예측했습니다. 심지어, 평균을 3.x개라고 예측하기도 했습니다만, 실제 결과는 상이하였습니다. 3번 문제였던 이 문제는 난이도가 그렇게 어려운 편이 아니였습니다. 그래서 문제 분석을 풀이보다 중점적으로 하고자 합니다. 먼저, 문제에서 구하고자 하는 것은 무엇인가요? 연산이 성공하면 1을, 아니면 0을 출력하라는 것입니다. 연산이 무엇인가요? R, W, X 중 하나임을 볼 수 있습니다. USER_NAME, FILE_NAME, operation 순서로 주어집니다. 그리고, 이것은 유저 USER_NAME이 파일 FILE_NAME인 파일에 대해 operation을 수행할 수 있는지를 의미함을 알 수 있습니다. 다시 문제를 이해해 봅시다. 구하고자 하는 것이 무..
구현 2022. 7. 3. 01:18
가희와 키워드 : equal 연산이 들어오면 hash 계열 구조를 이용해 봅시다.

제가 개최한 코딩테스트 2회의 2번 문제는 가희와 키워드 문제였습니다. 메모장에 있었던 키워드는 해당 키워드에 대한 글을 쓰고 나면 지워지게 되는데요. 문제는 블로그에 글을 쓰고 난 후, 메모장에 남은 키워드는 몇 개인지를 묻는 것입니다. 이 문제의 원래 출제 의도는 string의 길이 제한을 잘 보고 압축을 해서, 문자열 비교하는 복잡도를 떨궈낼 수 있는 가였습니다. 문제 제한을 더 자세히 보겠습니다. 문제에서 등장하는 키워드의 총 개수는 200만개 이하입니다. 200만개에 대해서 메모장에 키워드가 있는지를 검사하면 되므로, treemap을 써도 괜찮아 보이긴 합니다. O(200만log50만)면 괜찮지 않을까요? 여기서 문제. treemap을 쓰면 문자열의 compareTo 함수는 얼마나 호출이 될까요..
구현 2022. 2. 25. 16:52
java 다른 객체를 참조하는데 ==이 참인 경우가 있을까요?

java 강의에서 == 연산자에 대해, 이 글에서 언급을 했었습니다. 그런데, 질문을 받고 답변을 하다 보니, 헷갈리는 점이 있었습니다. 객체에서 다른 객체를 참조하는데 a == b인 경우가 있을까? 사실, 이에 대한 답은 문서에 있습니다. Object 클래스에 있는 equals 메서드에 나와 있는데요. 다른 부분은 없고, 초록색 부분과 노란색 부분만 읽어보시면 됩니다. x와 y가 같은 오브젝트를 참조한다를 명제 Q, Object 클래스의 equals 메소드가 true를 리턴한다를 명제 P라 합시다. if and only if는 필요 충분 조건을 나타냅니다. 즉, 저 메소드가 참 값을 리턴했다는 것은, x와 y가 같은 객체를 참조했다는 것입니다. 이런 경우에만 참이 된다는 소리입니다. x == y인데 다..
코딩/Java 2021. 3. 21. 01:16
언급이 좀 되는 모 자료구조의 보조 해시 함수에 대한 이야기

안녕하세요. chogahui05입니다. 자바의 해시맵은 hashCode를 기반으로 버킷의 어디에 들어갈지를 계산합니다. 그런데, putVal을 자세히 보셨다면 아시겠지만, hash function의 리턴값을 인자로 넣는 것을 알 수 있습니다. 이것은 어떻게 된 일일까요? java8에서 모 자료구조 코드를 조금씩 뜯어봅시다. get 메서드를 보시면, getNode를 호출합니다. 그리고, 이 메서드는 hash(key)를 인자로 삼습니다. 이것은 put도 마찬가지입니다. 내부적으로 putVal을 호출하고, 이것 역시 hash(key)를 호출합니다. 내부를 보시면, key.hashCode 값을 h에 넣습니다. 여기서, 해시코드는, 오버라이딩이 된 hashCode 값입니다. 그리고 이것과 다른 값을 비트 xor을..
레퍼런스/분석 2020. 9. 2. 22:25
해시맵에 있는 tiebreakorder는 어떤 메소드일까요?

HashMap 클래스는 내부적으로 RB tree를 씁니다. 이것을 적용하기 위해서는 compare, 즉 비교를 할 수 있는 비교자가 재정의가 되어야 하는데 (대표적으로 TreeMap, TreeSet 등이 있는데, 비교체 구현 없이 써 보면 어떤 일이 일어날지는..) , 우리는 굳이 그것을 정의하지 않고도 쓸 수 있었습니다. 어떻게 그런 일이 가능했을까요? 답은 tieBreakOrder 메소드에 있었습니다. 이 메서드에 대해 이해하기 전에, 아래 두 글을 읽고 오시는 것을 권장드립니다. [관련글] 왜 equals를 재정의하면 hashCode도 같이 재정의 해야 할까요? hashCode가 모두 같을 때 어떤 일이 일어날까요? 먼저 임의의 객체 하나를 만들어 보겠습니다. 이름은 MyObj라고 짓겠습니다. eq..
레퍼런스/분석 2020. 8. 28. 00:30