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

🚨문제 설명

💡푼 방법

나는 일단 for문으로 풀었는데 정답은 나오나 효율이 나오지 않아 실패로 떴다.

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        
        for(int i = 0; i < completion.length; i++){
            for(int j = 0; j < participant.length; j++){
                if(completion[i].equals(participant[j])){
                    completion[i] = "";
                    participant[j] = "";
                }
            }
        }
        
        for(int k = 0; k < participant.length; k++){
            answer += participant[k];
        }
        
        return answer;
    }
}

 

🚧오답노트

import java.util.HashMap;

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

이전에 for 문을 사용하면 최대 100,000명이 참가할 때 100,000승만큼(100억번) 돌아가서 효율이 나오지 않았던 것이다.

 

이후 hashmap을 이용하여 최대를 계산해보면 hashmap에 참가자를 100,000번 넣고(put) 완료자를 99,999번 넣은 후(put), 0이 아닌 키를 찾기 위해 100,000을 찾아(get) 100억번 돌던 코드가 최대 299,999만큼만 돈다.

 

효율을 높이기 위해서는 시간복잡도에 대해 더 공부해야할 것 같다.