-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
HashMap을 사용한 방법 맞는지 질문드립니다.
21.09.01 18:27 작성 조회수 173
0
안녕하세요.
강의 중 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';
}
답변을 작성해보세요.
0
답변 1