고양이 두 잔

Hash 배열은 빠른 검색 속도를 가지고 있으나 삽입/삭제 시 많은 비용이 소모된다. 이를 극복한 LinkedList는 삽입/삭제의 비용이 적지만 데이터가 많아질수록 검색에 비용이 많이 든다. 해시는 이를 극복하기 위해 도입된 개념이다. 해시, 해시 함수(Hash Function)란 임의의 길이를 갖는 임의의 데이터를 받아 고정된 길이의 데이터를 리턴하는 단방향 함수를 말한다. 가장 쉬운 예로는 나머지 연산자(%)가 있을 수 있겠다. 해시 함수의 특징은 아래와 같으며, 비교적 간단한 알고리즘으로 시스템 자원을 덜 소모한다, 즉 해시값 생성에 많은 시간이 들지 않는다. 해시값을 해독할 때는 많은 시간이 든다. 같은 입력 값에 대해선 같은 출력 값이 보장되며, 출력 값은 고르게 분포한다. 입력값이 아주 조금..

문제 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000..

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 각 문자열은 입력 순서대로 1부터 시작하는 번호를 부여받는다. 입력으로 주어지는 문자와 번호에 대해 대응하는 값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 문제의 개수 M (1 ≤ N, M ≤ 100,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열과 번호들이 주어진다. 입력으로 주어지는 문자열은 알파벳 대문자와 소문자로 이루어져 있으며, 길이는 최소 2, 최대 20이다. 또한 입력으로 주어지는 숫자는 1과 N 사이의 숫자이다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 출력 첫째 줄부터 차례대로 M개의 주에 문제에 대한 답을 출력..

Map Map 인터페이스는 Collection 인터페이스와는 다른 저장방식을 가진다. 키(key)와 값(value)을 하나의 쌍으로 저장하는 방식(key-value 방식)이 그것인데, 여기서 키(key)란 실질적인 값(value)을 찾기 위한 이름의 역할을 한다고 할 수 있다. 여기서 중요한 사실은 키는 중복저장될 수 없지만 값은 중복저장이 가능하다는 점이다. 만약 기존의 키와 같은 키에 다른 값을 저장하면, 값이 대체되는 효과가 발생한다. Map 인터페이스를 구현한 클래스는 HashMap, HashTable, TreeMap, SortedMap등이 있고, 공통으로 사용할 수 있는 메서드는 다음과 같다. HashMap HashMap 클래스는 Map 컬렉션 클래스에서 가장 많이 사용되는 클래스이다. Hash..