수요일, 9월 12, 2012

코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이


마지막 문제는 문제 자체를 이해하는게 어려웠네요. 어떤 분들은 바로 정확히 이해하시던데.... 비전공자라고 변명을 하면서.. ( 전산통계학과 ㅎㅎ )



문제만 이해하고 작성한 버전입니다. 문자가 하나만 차이나는 것인지 확인하는 함수를 만들고, 그것으로 리스트를 쭉 늘리면서 단어를 찾는 방법





그런데 이렇게 하면 속도가 엄첨나게 느리게 동작합니다. 그래서 일단 가장 많이 호출되는 oneDiff를 조금 개선 했습니다.


가끔 파이썬이 부족하다 싶을 때가 이런부분이 아니가 생각됩니다. 정말 조금 개선되었습니다. 그리고 다시 곰곰히 생각했습니다.

다시 생각해보니 oneDiff가 많이 호출이 되는 이유가 사전에서 문자가 하나 차이나는 집합을  가져올 때만 사용되는 것을 확인할 수 있었습니다.

그래서 새로운 사전을 만들었습니다. python의 dictionay 자료구조를 사용하여 해당 단어 키로 사용하고 값을 oneDiff 집합으로 가지는 사전을 만들었습니다.



key : 'aaas': 
value : ['aaas', 'alas', 'anas', 'caas', 'laas', 'paas', 'taas']

이런식으로 저장됩니다. 많이(?) 생각해서인지 많이(?) 개선되었습니다.
그런데 다른 문제가 발생했습니다. 몇 분만에 메모리 부족 에러~

현재까지 최종버전은 메모리를 사용하지 않고 File를 사용하도록 개선해보았습니다.
( 블로그 작성중에 보니... 47G 파일을 작성하고 있네요 -_-;;;; )


파이썬에선 정해진 크기의 배열일때는 List 보다 array가 훨씬 메모리를 적게든다고하여, 모든 단어를 숫자(key, 혹은 index)로 변경해서 다시 작성을 해보았지만 메모리 사용은 조금 줄었지만, 별반 차이 없음 -_-;




댓글 없음: