알고리즘 문제를 풀기위해 필수적으로 알아야 할 개념

브루트 포스(완전 탐색)으로는 시간초과에 빠지게 되는 문제에서는 해시를 적용시켜야함

N(1 ~ 100000) 의 값만큼 문자열이 입력된다.

처음 입력되는 문자열은 ‘OK’, 들어온 적이 있던 문자열은 ‘문자열 + index’로 출력하면 된다.

Input

5
abcd
abc
abcd
abcd
ab

output

OK
OK
abcd1
abcd2
OK

문제를 이해하는건 쉽다. 똑같은 문자열이 들어왔는지 체크해보고, 들어온 문자열은 인덱스 번호를 부여해서 출력해주면 된다.

하지만, 현재 N값은 최대 10만디ㅏ. 브루토 포스로 접근하면 N^2이 되므로 100억번의 연산이 필요해서 시간초과에 빠질 것이다. 따라서 ‘해시 테이블’을 이용해 해결해야 한다.

입력된 문자열 값을 해시 키로 변환시켜 저장하면서 최대한 시간을 줄여나가도록 구현해야 한다.

key 값을 얻어서 저장할 때, 서로다른 문자열이라도 같은 key 값으로 들어올 수 있다. 
(이것이 해시에 대한 이론을 배울 때 나오는 충돌 현상이다.)

충돌이 일어나는 것을 최대한 피해야하지만, 무조건 피할 수 있다는 보장은 없다. 
그래서 두번째 배열 값을 조금 넉넉히 선언해두는 것이다.

이를 고려해 final 값으로 선언한 해시 값은 아래와 같다.