[프로그래머스] 완주하지 못한 선수(Java)

• 제출한 코드

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

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(completion);
        ArrayList<String> completionList = new ArrayList<>(Arrays.asList(completion));

        for (String s : participant) {
            int id = bin_search(completionList, completionList.size(), s);
            if (id >= 0) {
                completionList.remove(id);
            }
            else return s;
        }
        return "";
    }

    public int bin_search(ArrayList<String> List, int n, String key){
        if(n==0) return -1;
        int pl=0;
        int pr = n-1;
        int pc;
        do{
            pc = (pl+pr) /2;
            if(List.get(pc).equals(key)) return pc;
            else if(List.get(pc).compareTo(key)<0) pl = pc+1;
            else pr = pc-1;
        } while (pl <= pr);
        return -1;
    }
}

처음에는 일치하는 이름의 인덱스를 찾기 위해 indexOf 메소드를 사용했다.

그런데 효율성 검사에서 시간 초과가 나서 인덱스를 찾는 과정을 이진 탐색으로 바꾸었다.

 

 

• 다른 사람의 풀이

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;
            }
        }
        return answer;
    }
}

HashMap을 사용하였는데, participant의 이름과 인원을 기록한 후 completion의 이름에 해당하는 key의 value를 -1한다.

HashMap의 value가 0이면 해당하는 key인 이름을 반환한다.

 

** getOrdefault(Object key, DefaultValue): 찾는 key가 존재하면 해당 키의 value를, 없으면 기본값을 반환

 

소감: 해시맵이라는 컬렉션에 익숙하지 않아서 전혀 생각하지 못했는데 두 가지 값이 동시에 필요한 문제가 있다면 해시맵을 사용하는 것을 고려할 수 있도록 노력해야겠다.