Making Anagrams

생각한 것

단순하게 생각해서 입력받은 문자열들을 글자 단위 쪼개 리스트로 만들어 비교해서 공통되는 문자를 카운팅 해서 기존 문자열에서 빼는 로직을 생각했었다. 문자열 a를 순회하면서 문자열 b에 포함된 문자열이 있으면 빼주는 식인데 문제가 있었다. 첫번째는 "어떻게 한 글자씩 뺄 것인가?"이고 두번째는 "String에서 한글자씩 제거할 때 드는 오버헤드의 크기"였다. 보통 String.replace()로 모든 글자를 치환하는 방식을 사용하는데 이번 문제에서는 한 글자씩 제거해나가야 했다. 그리고 한 글자씩 제거하기 위해 루프를 돈다면 O(m*n)의 시간복잡도를 가지게 되므로 비효율적이다.

개선

아나그램은 결국 공통된 문자를 같은 개수만큼 가지고 있으면 된다. 그러므로 문자와 그 개수를 기억하고 선형 시간안에 자료를 꺼낼 수 있는 맵을 사용하면 빠르게 카운팅 할수있다. 각 문자열을 맵에 담고 한번 순회하면서 공통 문자를 찾는다. 그리고 남은 문자들의 개수를 다 더해주면 제거해야하는 문자 개수가 나온다. 전부 선형시간 안에 동작하므로 O(m+n)의 시간복잡도를 갖는다.

여담

처음에는 최장 공통 부분수열(LCS)를 생각했었는데 아나그램이라는 특징이 있었기 때문에 해당 방법을 사용하면 안된다. LCS를 한번 더 짚고 싶었는데... 따로 공부해야겠다. 그리고 맵은 참 편한 자료구조이다.

 

추가 : 입력 데이터가 a-z의 알파벳이라는걸 적용해서 알파벳이 담기는 26개짜리 배열을 두개 선언해서 사용하면 맵을 쓰는거보다 리소스와 코드를 훨씬 줄일 수 있다.