[프로그래머스 알고리즘 고득점 Kit][해시][Java] 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

1.  틀린 코드

HashSet에 완주자를 저장하고 참가자 배열을 돌면서 완주자 집합에 없으면 완주하지 못한 선수라 생각하고 코드를 작성했다.문제를 제대로 안읽고 빠르게 풀려다 동명이인이 존재함을 인지하지 못했다.

import java.io.*;
import java.util.*;

class Solution {
    
    static HashSet<String> completions;
    
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        completions = new HashSet<>();
        for(String c : completion) {
            completions.add(c);
        }
        for(String p : participant) {
            if(!completions.contains(p)) {
                  answer = p; 
            }
        }

        return answer;
    }
}

2. 정답 코드

(1) 첫번째 방법 
N + N-1 + N -> O(N)

참가자 명단의 인원수를 저장해서 
완주하면 인원수를 하나씩 뺐다.

인원이 0이 아닌 선수는 완주하지 못함

import java.io.*;
import java.util.*;

class Solution {
    
    static HashMap<String, Integer> participants;
    static String answer;
    
    public String solution(String[] participant, String[] completion) {
        participants = new HashMap<>();
        for(String p : participant) {
            //key 있으면 value를 +1, 없으면 value에 1 
            participants.put(p, participants.getOrDefault(p, 0) + 1);
        }
        for(String c : completion) {
            //참가자 명단에 완주자 있으면 value에 -1
            if(participants.containsKey(c)) {
                participants.put(c, participants.get(c) - 1);
            }
        }
        for(String p : participant) {
            //참가자 중에 완주자 처리 후 인원이 남아 있으면 완주하지 못한 선수
            if(participants.get(p) != 0){
                answer = p;
                break;
            } 
        }

        return answer;
    }
}

 

(2) 두번째 방법
N + N-1 + 1 -> O(N)

위 코드에서 인원이 0인 선수를 바로바로 삭제한다면

마지막 루프를 돌면서 인원이 0인 사람을 찾지 않아도 된다.

참가자 - 완주자 = 1 이기 때문에 남은 참가자가 완주하지 못한 선수.

import java.io.*;
import java.util.*;

class Solution {
    
    static HashMap<String, Integer> participants;
    static String answer;
    
    public String solution(String[] participant, String[] completion) {
        participants = new HashMap<>();
        for(String p : participant) {
            //key 있으면 value를 +1, 없으면 value에 1 
            participants.put(p, participants.getOrDefault(p, 0) + 1);
        }
        for(String c : completion) {
            //남은 이원수 0 이면 참가자 명단에서 삭제 - 완주처리
            int left = participants.get(c) - 1;
            if(left == 0) {
                participants.remove(c);
            } else {
                participants.put(c, left);
            }
        }
        for(String a : participants.keySet()) {
            //마지막 한 사람이 완주하지 못한 선수
            answer = a;
        }

        return answer;
    }
}

근데 결과는 거의 똑같네... 마지막 루프가 없어지는 대신 remove 로직이 들어가서 그런듯

(3) 세번째 방법
NlogN + (N-1)log(N-1) + N-1 -> O(NlogN)

참가자와 완주자를 이름순서로 정렬 후 비교해서 찾는 경우

import java.io.*;
import java.util.*;

class Solution {
    
    static HashMap<String, Integer> participants;
    
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for(int i=0; i<completion.length; i++){
            if(!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }

	//마지막 참가자가 완주못했을 경우
        return participant[participant.length-1]; 
    }
}

프로그래머스 환경에 대한 연습이 필요하다는 생각을 했다.
내가 필요한 메서드가 생각나지 않으면 IDE cmd + 클릭으로 클래스 내부를 보며 찾았었는데
그러지 못하니까 내가 생각한 기능을 가진 메서드의 이름을 명확히 기억하지 못했다.

getOrDefault(key, default) -> key 있으면 value 가져오고, 없으면 defalut 값 value 에 넣기

keySet -> map의 key를 Set으로 반환 -> iterater 순회 가능