아이소그램(isogram), 중복된 문자 검열

이번 테스트는 상당히 쉬운 코딩테스트이지만 정답과 비교했을때 코드의 성능에 큰 차이가 있어 포스트하기로 했다.

 

문제는 상당히 간단하다. 문자열을 입력받아 중복된 문자가 있는지 없는지를 boolean 타입으로 반환하면 된다.

 

직접 작성한 코드

public class Solution {
    public boolean isIsogram(String str) {
        public boolean isIsogram (String str){
            String[] arr = str.toLowerCase().split("");

            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length - 1; j++) {
                    if (arr[i].equals(arr[j])) return false;
                }
            }
            return true;
        }
    }
}

처음 내가 작성한 코드이다. 반복문안에 반복문을 넣어 주었으며 이경우 시간 복잡도는 O(n*(n-1)/2)이다.

 

 

정답코드

public class Solution {
    public boolean isIsogram(String str) {
        if(str.length()==0) return true;
        HashMap<Character, Boolean> hashMap = new HashMap<>();
        str = str.toLowerCase();

        for(int i = 0; i< str.length(); i++){
            if(hashMap.containsKey(str.charAt(i))) return false;
            hashMap.put(str.charAt(i),true);
        }

        return true;
    }
}

정답코드의 경우 하나의 반복문으로 문자를 하나씩 해시맵에 등록하고 그 문자가 해시맵에 저장되 있는지 확인한다.

해시맵의 입력과 탐색은 모두 O(1) 이며 반복문을 사용하므로 O(n+1+1), 즉 O(n)이 된다. 

 

마무리

이처럼 인덱스 혹은 순서에 관여 받지 않고 해시맵의 key값이 주어저 어떠한 데이터의 중복을 확인할때 사용하면 좋을 듯하다. ex) 그래프의 순회 (DFS,BFS)