Programers - Hash [완주하지 못한 선수]

1. 문제

 

문제 설명

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

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

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participantcompletionreturn

[leo, kiki, eden]	[eden, kiki]	leo
[marina, josipa, nikola, vinko, filipa]	[josipa, filipa, marina, nikola]	vinko
[mislav, stanko, mislav, ana]	[stanko, ana, mislav]	mislav

입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

2. 내 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Hash_1 {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        // participant에 있는 String 변수를 하나씩 completion에 있는지 비교해본다.
        for (int i = 0; i < participant.length; i++) {
            boolean isInclude = false;
            // completion에 participant에서 나온 name이 있는 지 확인
            for (int j = 0; j < completion.length; j++) {
                // 있다면 isInclude true
                if (participant[i].equals(completion[j])) {
                    completion[j] = null;
                    isInclude = true;
                    break;
                }
            }
            // 만약 없었다면 없는 이름 반환.
            if (!isInclude) {
                answer = participant[i];
            }
        }
        return answer;
    }
}

- 테스트 케이스 통과, 시간복잡도 탈락

 

3. 다른 사람 풀이

import java.util.*;

public class Hash_1 {
    public String solution(String[] participant, String[] completion) {
        // participant 부분을 정렬하고
        Arrays.sort(participant);
        // completion 부분을 정렬한다.
        Arrays.sort(completion);
        // --> 문자열순으로 즉, 문자열 배열을 sort 함수로 정렬하면
        // 알파벳, 모음순으로 정렬이된다.
        // index를 빼주는 방법
        int i;
        // 완주자 수 만큼 비교한다.
        for (i = 0; i < completion.length; i++) {
            // 정렬된 과정에서 완주자는 참가자 의 한 부분이므로
            // 정렬을 하면 참가자 한명씩 완주자 리스트를 비교해본다.
            // 그럼 완주자리스트에 없는 참가자를 거를 수 있다.
            if (!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }
        return participant[i];
    }
}

- 일단 문자열 배열에서 sort를 사용하면 문자열이 알파벳, 모음순으로 정렬된다.

- 참가자 리스트와 완주자 리스트를 정렬하면 애초에 완주자 리스트에 없는 참가자가 나오는순간

정렬이 비교가 안된다.

- 해당 부분을 리턴한다.

 

하지만 이코드는 Hash map을 사용하지 않은 방법이다.

 

3. 다른 사람 풀이 - 2 (Hashmap을 이용한 풀이)

import java.util.*;

public class Hash_1 {
    public String solution(String[] participant, String[] completion) {
        String string = "";
        // HashMap 선언
        HashMap<String, Integer> hm = new HashMap<>();
        // 참가자모두에게 value 값을 1을 준다. 만약 이름이 중복된 참가자가 있다면 기존 값에서 + 1을 추가한다.
        for (String player : participant) {
            if (hm.containsKey(player)) {
                hm.put(player, hm.get(player) + 1);
            }
            else{
                hm.put(player, 1);
            }
        }
        // 완주자들은 키값을 -1 한다.
        for (String player : completion) {
            hm.put(player, hm.get(player) - 1);
        }

        // 완주자들은 키값이 모두 0일 것이나 완주하지 못한 이들은 키값이 0 이상일 것이다.
        for (String player : hm.keySet()) {
            if (hm.get(player) > 0) {
                string = player;
            }
        }

        return string;
    }

    public static void main(String[] args) {
        String[] participant = {"leo", "kiki", "eden"};
        String[] completion = {"eden", "kiki"};
        Hash_1 hash_1 = new Hash_1();
        System.out.println(hash_1.solution(participant, completion));
    }
}

- 코드를 보면 먼저 participant들을 먼저 다 hashmap에 집어 넣고 값을  1넣어주고

중복된 참가자가 있다면 기존값에서  + 1을 추가한다.

- 완주자들은 hashmap에 키가 있다면 - 1을해서 완주자가 있는 키값은 0이 되게 만들어주고

중복된 이름의 참가자가 완주를 못할 경우 > 0 가 된다.

 

따라서 >0 의 조건으로 완주자가 아닌 자를 걸러내면된다.

 

1. hashmap.containsKey(key)

- 키가 있는지 없는지 boolean값을 반환한다. 있으면 true, 없다면 false를 반환

 

2. hashmap.keySet()

- hashmap에 들어있는 모든 키들을 List로 반환한다.

 

3. hashmap.get(key)

- hashmap에 key가 들어있는 키값을 반환하는데 key값이 없다면 null을 반환한다.

 

4. hashmap.getOrDefault(key, integer Valule)

- hashmap에 키를 넣었을 때 없다면 Value 값을 넣고 있다면 해당 키값을 반환한다.

 

 

JS

function solution(participant, completion) {
    let map = new Map();
    // hash map을 사용해서 참가자들을 등록하되 이미 중복된 이름이 있다면 기존값보다 + 1을 추가한다.
    for(let player of participant){
        if(map.has(player))
            map.set(player, map.get(player) + 1);
        else{
            map.set(player, 1);
        }
    }
    // 완주자들만 - 1을 해서 중복된 완주하지 못한자만 걸러낸다.
    
        map.set(player, map.get(player) - 1);
    }
    // 중복된 사람은 2 혹은 그보다 많은 value값을 가지고 있어서 - 1을 해도 걸러진다.
    for(let player of completion){
    for(let player of map.keys()){
        if(map.get(player) > 0){
            return player;
        }
    }

}

let participant = ['mislav', 'stanko', 'mislav', 'ana'];
let completion = ['stanko', 'ana', 'mislav'];

console.log(solution(participant, completion));

array의 원소는 원소값으로 접근할수 없고 indexOf 라는 함수로 해당 원소의 index를 알아낸다음

arr[index]형태로 접근해야한다.

 

또한 삭제도 splice(index, 1) 이라는 형태로 제거해야한다.