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) 뭐든 알고리즘이란 상황에 맞게 구성해야 한다.
'Computer Science > 알고리즘' 카테고리의 다른 글
33. 문자열 매칭 알고리즘 - 전수조사법(Brute Force) (0) | 2016.08.03 |
---|---|
32. Floyd's 알고리즘(DP 방식으로 최단 경로 찾기 알고리즘) (0) | 2016.07.20 |
30. Hash Separate Chaining(해시+링크드리스트) 구현 알고리즘 (5) | 2016.07.16 |
29. 가장 긴 공통 부분 문자열(LCS, Longest Common Subsequence) 찾기 알고리즘 (0) | 2016.07.09 |
28. 피보나치 수열( 재귀, 동적 프로그래밍, 반복) 모든 방식 알고리즘 (0) | 2016.07.01 |