[Algorithm/Programmers] 자바 - 완주하지 못한 선수

풀이

그렇다고 합니다. 오직 단 한 명의 선수를 제외한 모든 선수가 완주하였습니다.
간단히 생각해도 주어진 입력 participant과 completion를 비교해보면 participant의 크기보다 completion의 크기가 1만큼 작을 것입니다.

• participant size : n
• completion size : n - 1
• completion은 participant에 속해있습니다.

• 입력이 엄청 크진 않습니다.
• 이름 문자열의 수는 1~20이고, 소문자로만 이루어져 있으므로 대소문자를 구분할 필요는 없습니다.
• 참가자 중 동명이인이 있다고 합니다. 이와 관련된 예외를 특히 주의해야 할 것 같습니다.

1. 정렬을 이용한 풀이

/**
 * 정렬을 이용한 문자열 비교 풀이
 */
private static String getPersonBySort(String[] participant, String[] completion) {
    // 1. Sort the array in ascending order.
    Arrays.sort(participant);
    Arrays.sort(completion);

    // 2. Compare strings in two sorted arrays.
    int len = completion.length;
    for (int i = 0; i < len; i++) {
        if (!participant[i].equals(completion[i])) {
            return participant[i];
        }
    }

    // 3. If at the end
    return participant[len];
}

간단한 아이디어에서 출발한 풀이입니다.

두 배열에서 오직 한 문자만 다르므로,
1. 정렬을 할 시
2. 두 배열의 인덱스 순서에서 문자열이 다른 경우 participant의 에 있는 문자가 completion에 없는 것을 뜻합니다.
3. 문자열의 길이가 작은 completion의 크기를 기준으로 비교하므로 다른 경우를 발견하지 못했다면, 비교하지 못한 participant의 마지막 인덱스가 완주하지 못한 선수입니다. (무조건 완주하지 못한 선수가 한 명 있으므로)

Time Complexity

1. Arrays.sort()는 내부적으로 Dual-Pivot QuickSort로 구현되어 있으며 모든 데이터 타입에 대해서 $O(nlogn)$ 입니다.
2. 배열의 길이만큼 단순 비교입니다. $O(n)$

   $O(nlogn) + O(nlogn) + O(n) = O(nlogn)$

2. HashMap을 이용한 풀이

/**
 * HashMap을 이용한 풀이
 */
private static String getPersionByHashMap(String[] participant, String[] completion) {
    HashMap<String, Integer> hashMap = new HashMap<>();

    // 1. Put the participant array to the hashmap while increasing the value.
    for (String person : participant) {
        hashMap.put(person, hashMap.getOrDefault(person, 0) + 1);
    }

    // 2. Put the participant array into the hashmap while reducing the value.
    for (String person : completion) {
        hashMap.put(person, hashMap.get(person) - 1);
    }

    // 3. Find a key whose value is not 0.
    String ans = "";
    for (Entry<String, Integer> entry : hashMap.entrySet()) {
        if (entry.getValue() > 0) {
            ans = entry.getKey();
            break;
        }
    }
    return ans;
}

1. 참가자를 key로 해당 참가자(key)의 수를 value로 paritipant 배열의 모든 원소를 HashMap에 넣습니다. (동명이인이 있을 수 있으므로 같은 이름(key)을 가진 value를 늘려 모든 원소에 대해 비교한다.)
2. completion 배열의 원소들을 hashMap에서 value를 1씩 줄여줍니다.
3. value가 0이 아닌 키 값을 찾습니다. (오직 한 원소만 다르므로)
   • value를 계속 확인해야 하므로 keySet()보다는 entrySet()을 사용하는 것이 좋습니다.

Time Complexity

1. hashMap은 탐색, 입력과 삭제에 대해 $O(1)$, 최악의 경우 $O(n)$을 갖습니다.
   - Java 8 부터는 최악의 경우 $O(logn)$을 보장합니다.

   $O(logn) + O(logn) + O(logn) = O(logn)$

• 이 부분에 대해 명확히 이해하지 못한 부분이 있어 틀릴 수 있습니다. hashmap time complexcity를 참고하시길 바랍니다.

+a

• HashMap은 Map을 구현합니다. Key, Value를 묶어 하나의 Entry로 저장합니다. 그리고 Hashing을 사용하기 때문에 검색에서 뛰어난 성능을 보입니다.
  - 탐색, 입력과 삭제에 대해 평균 $O(1)$, 최악의 경우 $O(n)$
  - Java 8 부터는 최악의 경우 $O(logn)$을 보장합니다.
  • 순서에 상관 없이 저장됨
  • Null을 허용함
  • thread-safe를 보장하지 않음
    • => 필요 시 HashTable or ConcurrentHashMap 사용
• getOrDefault(Object key, V DevalutValue)
  - key : 값을 가져와야 하는 요소의 키입니다.
  • defaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본 값입니다.

References

• 자바 11 공식문서 - getOrDefault()
• [자료구조] 코드로 알아보는 java의 Hashmap
  
• Stack Overflow - Hashmap Time Complexity