- 코딩테스트 풀이
https://programmers.co.kr/learn/courses/30/lessons/42576?language=java#_=_
- Nora 풀이
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
ArrayList<String> participantList = new ArrayList<>(Arrays.asList(participant));
ArrayList<String> completionList = new ArrayList<>(Arrays.asList(completion));
completionList.forEach(x->{participantList.remove(x);});
return participantList.get(0);
}
}- 질문
카테고리 항목이 해쉬인데, 해쉬로 처리하는게 더 효율적인가요?
제가 작성한 arraylist를 활용한 방법이 효율적인가요?
참고 : https://velog.io/@qweadzs/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98
(hashmap 을 이용한 풀이)
- 답변
list : root node 를 시작으로 순차적으로 일치 여부를 검사 O(n)
map : hash 함수에 의해 계산되어 나온 위치에 데이터 존재여부 확인 O(1)
리스트의 경우 찾고자 하는 데이터가 나올 때 까지 순차적으로 검색합니다.
즉, A집단에서 B집단의 요소들을 찾고자 한다면. 최악의 경우 A*B 정도의 검색이 일어날 수 있습니다.
무언가를 검색할 때, list 보다는 hashmap을! 그리고 arraylist sort할 때, 그 작업을 위해 내부에서 엄청난 작업을 하고 있으며... 효율성을 생각할 때는 많은 걸 고려해봐야한다..
- 숙제
HashMap 이 성능이 굉장히 좋은데 왜 다른 자료구조를 쓸까요?
List 와 함께 차이점을 정리해 보세요
HashMap은 해싱(hashing)이란 검색 방법을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보여준다.
그러나 키 값 중복을 허용하지 않으므로 키 값이 중복되는 경우 값을 저장하지 않는다.
Map의 특성 상 빈 공간을 찾아서 저장하기 때문에 List보다는 데이터 저장속도가 느릴 수 있다.
List는 순차적으로 데이터를 저장하며, 값을 저장할 때 중복된 값을 저장할 수 있다.
또, HashMap처럼 키가 중복되어 값이 저장이 안되는 경우가 발생하지 않는다.
그러나 검색 시, root node 를 시작으로 순차적으로 일치 여부를 검사하므로 성능이 좋지는 않다.
따라서 단순히 값을 순서대로 저장하고 출력하는 경우에는 List를 사용하고,
특정 키값을 가지고 값을 빠르게 찾고 싶을 때는 Map을 사용하면 된다.
HashMap은 데이터 양이 적더라도 해시 값과 주소를 저장하는 일정 크기의
burket을 가지고 있어야 하기 때문에 리소스를 많이 사용하는 단점이 있다.
burket 크기가 10이라면 3개만 사용하더라도 버킷 크기 10이 모두 존재해야하므로 낭비가 될 수 있다.
그러나 List는 자기자신의 size대로 리소스를 사용하기 때문에 HashMap보다는 덜 사용한다.
따라서 각 프로그램 데이터 구조에 맞게 알맞은 자료 구조를 사용해야한다.
