31. Hash 기초 문제 (1) 문자열에서 중복 문자 제거 알고리즘

1. 개요

 이 알고리즘은 무척 쉬움.

 문자열에서 중복되는 문자를 제거하는 알고리즘은 크게 3가지 방법이 존재.

 

(1) O(n^2) 풀이 

 문자열의 첫 문자를 기준으로 문자열 끝까지 반복문자를 제거, 이 과정을 n번 반복.

 O(n) * O(n) = O(n^2)

(2) O(nlogn) 풀이

 문자열을 정렬, 이 후 문자열 처음부터 반복되는 문자 제거.

 O(nlogn) + O(n) = O(nlogn)

 만약, 문자열 정렬을 버킷 정렬처럼 O(n)에 정렬할 수 있다면 O(n) 소요.  

 

(3) O(n) 풀이

 문자열을 시작부터 해시 테이블에 저장, 만약 값이 존재한다면 다음 단계 진행.

 O(1) * O(n) = O(n)

 

2. 문제

 한 문자열에서 반복 문자를 제거하는 알고리즘을 작성하시오.

 단, 반복 정렬 해시 기법을 모두 사용하여 작성하시오.

3. 코드

3-1) 메인

3-2) rmvDuplicationByFor()

3-3) rmvDuplicationBySort()

3-4) rmvDuplicationByHash()

3-5) 출력

4. 정리

 먼저 결과는 정상적으로 출력된다.

 하지만 소요 시간은 데이터 개수가 늘어날 수록 이론과는 정반대로 움직이고 있다.

 그 이유는 아마 크기가 커질수록 생성과 삭제 시간에 더욱 많은 시간이 소요되고, 

 생성과 삭제가 필요없는 반복적인 방법이 더 빠르게 나타나는듯 하다.

 

 이런 단순한 문제에서는 해시 기법의 유용함을 보이지는 못했지만 O()의 시간은 최악의

 경우를 상정한 시간이기에 이론과 다를 수 있다.

 (하지만 생각보다 너무 차이가 심하게 난다 ㅠㅠ, 연구해 봐야겠다.)

 앞으로 조금 더 복잡한 문제에서 해시 기법의 유용함을 보이도록 한다.

 기억해야 할 것

 (1) 데이터 개수가 작으면 그냥 추가 메모리 자원이 소요되지 않는 단순한 방식으로 작성하자.

 (2) 뭐든 알고리즘이란 상황에 맞게 구성해야 한다.