인프런 커뮤니티 질문&답변

안녕하세요.

강의 중 HashMap을 사용하면 O(n)으로 풀이 할 수 있다고 하셔서 풀어보았습니다. 이 방법이 O(n) 맞나요?

    private static char solution(int n, int[] nArr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int x : nArr) {
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (map.get(x) >= 2) {
                return 'D';
            }
        }

        return 'U';
    }

위 방법이 O(n)이 맞다면, test결과 속도가 아래와 같이 이중 for문으로 풀이한 것이 속도가 더 빠른데, 그래도 코딩테스트 풀이할때는 O(n) 방법으로 풀이하는 것이 올바른거겠죠??

아니면 혹시 HashMap의 getOrDefault 내부에서 for문이 돌아가서 O(n)이 아닌건지.. 궁금합니다!

    private static char solution(int n, int[] nArr) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nArr[i] == nArr[j]) {
                    return 'D';
                }
            }
        }

        return 'U';
    }