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

백준 알고리즘 강의 순서대로 풀다가

지루해서 프로그래머스로 넘어가 봤다.

 

programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

 

일단 테마가 hash 이긴 했으나

1차적으로 생각이 난 건 2중 for문

 

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

짜면서도 효율성 테스트 통과는 힘들겠다 싶었는데

역시는 역시ㅋㅋ

 

타이틀대로 hashMap 이용해서 다시 짜 봤다.

hashMap 쓰기 애매하다 생각한 이유는

참가자 중에 같은 이름이 여럿 일 수 있다는 조건 때문이었다.

key는 중복이 안되니까.

 

그래서 key는 참가자 이름으로 가고 value에 몇 명인지 count 해주는 방식으로 개선.

출력은 count가 0 초과 인 key를 출력하는 것으로 변경했다.

 

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> partMap = new HashMap<>();
        for(int i=0; i<participant.length; i++){
            if(partMap.containsKey(participant[i])){
                partMap.put(participant[i], partMap.get(participant[i])+1);
            }else{
                partMap.put(participant[i], 1);
            }
        }
        for(int i=0; i<completion.length; i++){
                if(partMap.containsKey(completion[i])){
                    int cnt = partMap.get(completion[i])-1;
                    partMap.put(completion[i], cnt);
                }
        }

        Iterator<String> it = partMap.keySet().iterator();
        while(it.hasNext()){
            String key = it.next();
            if(partMap.get(key) > 0){
                answer = key;
                break;
            }
        }
        return answer;
    }
}

 시간 복잡도 n^2 -> n 으로 개선됐다.

 

다른 사람의 풀이에서 보니 

두 배열을 정렬해 completion으로 1단 for문을 돌리는데

서로 다른 값이 나오면 paritipant 값을 리턴하는 방법도 있었고, 

getOrDefault라는 function을 쓴 알고리즘도 보였다.