[Java] 완주하지 못한 선수

완전탐색 : 모든 경우의 수를 시도하는 방법
two pointer

해시 함수(Hash Function)

• 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
• 입력받은 데이터를 해시 값으로 출력시키는 알고리즘

완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다.
단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

배열 participant와 배열 completion 만들기
완주하지 못한 선수 구하기 = 전체 참가자 - 완주자

• 정렬(Sort)을 사용할 경우 코드는 간결하지만, 시간복잡도가 O(n)(단순탐색) => O(nLogN) ~ O(n^2)로 늘어난 단점이 있다.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

100,000 = 10^5
10^5의 경우 n^2으로 풀 수 없다.

• completion의 길이는 participant의 길이보다 1 작습니다.

전체 참가자 : participant
완주자 : completion
즉, completion.length = participant.length - 1

• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

• 참가자 중에는 동명이인이 있을 수 있습니다.

중복제거 안 함

방법 1. Arrays와 이중 for문

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        // 1. 두 배열을 정렬한다.(nlogn)
        Arrays.sort(participant);
        Arrays.sort(completion);

        // 2. 두 배열이 다를 때까지 찾는다.
        // i 0~ n-1 순회(0(n))
        for(int i=0; i < completion.length; i++) {
            if(!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }
        // 3. 완주하지 못한 마지막 주자
        return participant[participant.length-1];


    }
}

방법2. Hash

해시(Hash)는 키 값이 배열 인덱스로 변환되고,
그 배열 인덱스를 사용해서 검색, 삽입, 삭제 등이 빠르며 중복 제거에 유용하다.
하지만 순서 있는 배열에는 어울리지 않으며 해시 함수의 의존도가 높다.

해시맵 사용법 : 선언과 값 추가

HashMap<Integer,String> map = new HashMap<>(); //new에서 타입 파라미터 생략가능
map.put(key,value); //값 추가

• 선언 시 HashMap에 설정해준 타입과 같은 key와 value값을 넣어야하며
  만약 입력되는 키 값이 HashMap 내부에 존재한다면 기존의 값은 새로 입력되는 값으로 대치된다.

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String,Integer> map = new HashMap<>();
        
        for(String player : participant) map.put(player, map.getOrDefault(player,0)+1);
        for(String player : completion) map.put(player, map.get(player)-1);
        
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if(entry.getValue() !=0){
                answer = entry.getKey();
                break;
            }
        }
        
        return answer;
    }
}