#25😊 완주하지 못한 선수

2023.02.20 - [자료구조 및 알고리즘] - #8 해시테이블 - 개념(해시, 해시 함수) / ChatGPT 사용해봄

#8 해시테이블 - 개념(해시, 해시 함수) / ChatGPT 사용해봄

- 위의 글의 내용을 바탕으로 문제를 풀었다.

---

[문제]

출처 : https://school.programmers.co.kr

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

---

[해설]

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, ArrayList<String>> map = this.makeParticipantMap(participant);
        return this.deleteParticipant(map, completion);
    }

    private Map makeParticipantMap(String[] participant) {
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        
        for(int i = 0; i < participant.length; i++) {
            ArrayList<String> list = new ArrayList<String>();
            if(map.containsKey(participant[i])) { // 동명이인
                list = map.get(participant[i]);
            }
            list.add(participant[i]);
            map.put(participant[i], list);
        }
        return map;
    }
    
    private String deleteParticipant(Map<String, ArrayList<String>> map, String[] completion) {
        for(int i = 0; i < completion.length; i++) {
            if(map.get(completion[i]).size() < 2) {
                map.remove(completion[i]); // 동명이인 없으면 바로 remove
            } else {
                // 동명이인
                ArrayList<String> partici_list = map.get(completion[i]);
                partici_list.remove(partici_list.size() - 1);
                map.put(completion[i], partici_list);
            }   
        }
        
        Iterator<String> keys = map.keySet().iterator();
        if(keys.hasNext()) {
            return keys.next();
        } else {
            return "";    
        }
    }
}

- 아래와 같은 식으로 key-value 구조를 생각했다.

- 마라톤에 참가한 선수 명단이 아래와 같을 때 각 선수의 이름을 key, value 또한 각 선수의 이름으로 했다.

- marina와 nikola 같이 동명이인이 참가한 상황이라면 value에 2개 이상의 값을 할당해야 하는데 이때는 ArrayList를 활용했다.

- 위에 링크한 해시테이블 글을 보면 연결리스트(Linked List)를 이용하라는데 ArrayList로 그냥 갑자기 하고 싶어서 뭐 그렇게 됐다.

- 굳이 말하자면 아래의 key-value 구조를 만드는 해시함수의 원리는 input으로 주어지는 이름을 기준으로 값을 분류하는 것이다.

참가한 선수 명단 : ["marina", "marina", "josipa", "nikola", "nikola", "vinko", "filipa"]

 

cf) Map의 getOrDefault method를 사용한 예시(이게 성능이 조금 더 좋았다.)

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer ="";
        HashMap<String, Integer> hm = new HashMap<>();
        for(String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for(String player : completion) hm.put(player, hm.get(player) -1);
        for(String key : hm.keySet()) {
        	if(hm.get(key) != 0) {
        		answer = key;
        		System.out.println(answer);
        		break;
        	}
        }
        return answer;
    }
}