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

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

프로그래머스

 

 

풀이방법

 

2025.03.27

참가자 명단에는 있지만 완주자 명단에는 없는 선수의 이름을 찾아내야 한다.

그 선수는 반드시 한 명이다.

 

명단에는 동명이인이 존재할 수 있다. 따라서 Set을 썼다가는 동명이인을 잡아내지 못해 틀릴 가능성이 높다.

 

푸는 과정에서, 정확도 테스트를 모두 통과한 코드를 총 4가지 작성해보았다. 아래와 같다.

 

첫 번째 시도: ArrayList 사용

참여자 명단의 모든 요소를 ArrayList에 넣은 뒤, 완주자 명단의 모든 요소를 ArrayList에서 remove()한다.

remove()되지 않고 남아있는 이름이 정답이다.

이 방법은 효율성 테스트를 전혀 통과하지 못했다.

 

두 번째 시도: HashMap 사용

참여자 명단에 각 이름이 등장하는 횟수를 HashMap<이름, 횟수>를 이용해 센다.

완주자 명단에 각 이름이 등장하는 횟수를 HashMap<이름, 횟수>를 이용해 센다.

두 배열을 비교하여 등장 횟수가 다른 이름을 찾는다. 그 이름이 정답이다.

이 방법은 효율성 테스트를 1개 케이스만 통과했다.

 

세 번째 시도: 1차원 배열 사용

참여자 명단과 완주자 명단을 정렬한다.

0번 인덱스부터 완주자 명단의 끝 인덱스까지 차례대로 두 배열을 비교한다.

일치하지 않는 요소가 발견되면, 그 값이 정답이다.

완주자 명단을 끝까지 다 보았는데 모두 일치했다면, 참여자 명단의 마지막 요소가 정답이다.

효율성 테스트를 전부 통과했다.

 

네 번째 시도: HashMap 사용 (로직 개선)

참여자 명단에 각 이름이 등장하는 횟수를 HashMap<이름, 횟수>를 이용해 센다.

완주자 명단을 처음부터 끝까지 돌며, 이름의 등장 시마다 참여자 명단에서 해당 이름의 등장 횟수를 1 뺀다.

위 과정을 완료한 뒤에 등장 횟수가 0이 아닌 1인 유일한 이름이 정답이다.

효율성 테스트를 전부 통과했다.

 

첫 번째와 두 번째 코드가 느렸던 이유:

첫 번째 시도에서는 ArrayList의 remove()를 반복 실행한다. ArrayList의 remove()는 시간복잡도가 O(N)이기 때문에 느리다!

두 번째 시도에서는 HashMap을 사용한다. HashMap의 조회 시간복잡도는 O(1)이지만, 로직의 효율성이 떨어진다. 로직을 개선한 네 번째 코드는 효율성 테스트를 통과했다.

 

코드

Java(2025.03.27) - 정확도 만점, 효율성 빵점 코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        List<String> list = new ArrayList<String>(Arrays.asList(participant));
        
        for(int i=0; i<completion.length; i++) {
            list.remove(completion[i]);
        }
        
        return list.get(0);
    }
}

 

 

Java(2025.03.27) - 정확도 만점, 효율성은 한 케이스만 통과한 코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Map<String, Integer> pMap = new HashMap<String, Integer>();
        for(int i=0; i<participant.length; i++) {
            String name = participant[i];
            if(pMap.containsKey(name)) pMap.put(name, pMap.get(name) +1);
            else pMap.put(name, 1);
        }
        
        Map<String, Integer> cMap = new HashMap<String, Integer>();
        for(int i=0; i<completion.length; i++) {
            String name = completion[i];
            if(cMap.containsKey(name)) cMap.put(name, cMap.get(name) +1);
            else cMap.put(name, 1);
        }
        
        for(String key: pMap.keySet()) {
            if(!cMap.containsKey(key)) {
                answer = key;
                break;
            } else if (cMap.get(key) != pMap.get(key)) {
                answer = key;
                break;
            }
        }
        
        return answer;
    }
}

 

 

Java(2025.03.27) - 정확도와 효율성 모두 만점을 받은 코드 (배열 사용)

import java.util.*;

class Solution {
    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])) continue;
            return participant[i];
        }
        return participant[participant.length-1];
    }
}

 

 

Java(2025.03.27) - 정확도와 효율성 모두 만점을 받은 코드 (HashMap 사용)

import java.util.*;

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