[Level 1] 완주하지 못한 선수 (Java)

문제는 해시 카테고리에 있지만 sort를 이용해서 풀었었다. 아래는 sort를 이용해 풀었을 때의 코드와 정확성 및 효율성 테스트 결과이다.

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%EB%AA%BB%ED%95%9C%EC%84%A0%EC%88%98_sort.java

public String solution(String[] participant, String[] completion){
    Arrays.sort(participant);
    Arrays.sort(completion);

    int i=0;
    for(i=0; i<completion.length; i++){
      if (!participant[i].equals(completion[i])){
      	return participant[i];
      }
    }
    return participant[i];
}

sort를 이용한 풀이

그리고 아래는 hash를 이용해 풀었을 때의 정확성 및 효율성 테스트 결과이다.

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%EB%AA%BB%ED%95%9C%EC%84%A0%EC%88%98_hash.java

GitHub - banjjak2/Programmers

public String solution(String[] participant, String[] completion){
    String answer = "";
    HashMap<String, Integer> hm = new HashMap<String, Integer>();

    for (String string : participant) {
      if (hm.get(string) == null){
          hm.put(string, 1);
      }
      else{
          hm.put(string, hm.get(string) + 1);
      }
    }

    for (String string : completion) {
    	hm.put(string, hm.get(string) - 1);
    }

    for (Map.Entry<String, Integer> entry : hm.entrySet()) {
      if (entry.getValue() != 0){
          answer = entry.getKey();
          break;
      }
    }

    return answer;
}

hash를 이용한 풀이

효율성 테스트를 보면 메모리 양은 비슷하지만, 시간을 비교했을 때 상당한 시간 차이가 발생했었다. 내가 사용한 Arrays.sort 메소드는 내부적으로 TimSort 알고리즘을 사용하는데, 이 알고리즘은 Merge Sort 알고리즘을 기반으로 작성되었으며, Insertion Sort 알고리즘과 Merge Sort 알고리즘의 결합 형태라고 한다. 

https://d2.naver.com/helloworld/0315536

HashMap의 경우 Key, Value 형식으로 구현이 되어 있는데, 키값을 알면 바로 Value 값을 알 수 있기 때문에 속도가 빠른 것으로 판단된다. 

https://d2.naver.com/helloworld/831311

각 Sort 알고리즘 및 데이터 구조의 시간 복잡도는 아래와 같다.