[알고리즘] 프로그래머스 - 완주하지 못한 선수 (Java)

문제 : programmers.co.kr/learn/courses/30/lessons/42576

 

처음 풀었을 때 코드

import java.util.*;

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

        for(int i=0; i<participant.length; i++){
            for(int j=0; j<completion.length; j++){
                if(participant[i].equals(completion[j])){
                    participant[i] = " ";
                    break;
                }
            }
        }
        for(int i=0; i<participant.length; i++){
            if(!participant[i].equals(" "))
                answer = participant[i];
        }
        
        return answer;
    }
}

 

중첩된 for문을 쓰기 때문에 복잡도가 O(n*n)이 되기때문에 코드 효율성이 낮다.

해시를 사용하면 빠르고 효율적으로 해결 할 수 있다고 하여 HashMap을 공부하고 다시 풀어보았다.

 

 

HashMap을 적용한 코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> h = new HashMap<>();
       
        for(String partic : participant){
            if(h.get(partic) == null)
                h.put(partic, 1); 
            else{	
            // 중복된 이름인 경우 value 값을 하나 더해준다
                h.put(partic, h.get(partic)+1);
            }
        }

        for(String comple: completion){
        // 참가자 명단에 있는 이름인 경우에는 value값을 하나 빼준다
            if(h.get(comple) != null)	
                h.put(comple, h.get(comple)-1);
        }
 
        for(String key : h.keySet()){
            if(h.get(key) != 0){
                answer = key;
            }
        }
        
        return answer;
    }
}