[코딩테스트 + Java] 완주하지 못한 선수 - 프로그래머스 Lv.1

🔗 문제 링크

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

---

📌 문제 요약

• 마라톤에 참여한 선수 목록 participant[]와 완주한 선수 목록 completion[]이 주어집니다.
• 단, 한 명만 완주하지 못했으며, 이름은 중복될 수 있습니다.
• 완주하지 못한 선수의 이름을 구해야 합니다.

---

✅ 풀이 1: 정렬 + 비교

💡 아이디어

• 두 배열을 정렬한 후, 순차적으로 비교하다가 다른 값이 나오면 그 사람이 완주하지 못한 사람입니다.
• completion은 항상 participant보다 1명 적기 때문에, 끝까지 비교했는데 차이가 없으면 마지막 사람이 정답입니다.

🧾 코드

public static String solution(String[] participant, String[] completion) {
    Arrays.sort(participant);
    Arrays.sort(completion);
    for (int i = 0; i < participant.length; i++) {
        if (i == completion.length || !participant[i].equals(completion[i])) {
            return participant[i];
        }
    }
    return "";
}

✅ 시간복잡도

• 정렬: O(n log n)
• 비교: O(n)
• 전체: O(n log n)

---

✅ 풀이 2: HashMap을 이용한 개수 비교

💡 아이디어

• 참가자의 이름을 map에 이름별 개수로 저장
• 완주자 이름을 순회하며 해당 이름의 개수를 1씩 감소
• 개수가 1인 사람이 완주하지 못한 사람

🧾 코드

public static String solution2(String[] participant, String[] completion) {
    Map<String, Integer> map = new HashMap<>();
    for (String p : participant) {
        map.put(p, map.getOrDefault(p, 0) + 1);
    }
    for (String c : completion) {
        map.put(c, map.get(c) - 1);
    }
    for (String name : map.keySet()) {
        if (map.get(name) == 1) return name;
    }
    return "";
}

☝️ merge()를 쓰는 방식도 있지만, 여기서는 getOrDefault()가 더 직관적일 수 있습니다.

✅ 시간복잡도

• map 구성: O(n)
• 완주자 반영: O(n)
• 전체: O(n)
  → 정렬 방식보다 더 빠름

---

⚖️ 두 풀이 비교

항목	풀이 1 (정렬)	풀이 2 (HashMap)
시간복잡도	O(n log n)	O(n)
중복 처리	O (정렬로 해결)	O (개수로 해결)
코드 난이도	간단함	약간 복잡하지만 더 빠름
확장성	제한적	더 일반적인 문제에도 사용 가능

---

🧪 테스트 케이스

public static void main(String[] args) {
    // 정상 결과: "leo"
    System.out.println(solution(new String[]{"leo", "kiki", "eden"}, new String[]{"eden", "kiki"}));
    // 정상 결과: "vinko"
    System.out.println(solution(new String[]{"marina", "josipa", "nikola", "vinko", "filipa"}, new String[]{"josipa", "filipa", "marina", "nikola"}));
    // 정상 결과: "mislav"
    System.out.println(solution(new String[]{"mislav", "stanko", "mislav", "ana"}, new String[]{"stanko", "ana", "mislav"}));
    // 정상 결과: "b"
    System.out.println(solution(new String[]{"a", "b", "a", "c", "d"}, new String[]{"a", "a", "c", "d"}));
    // 정상 결과: "b"
    System.out.println(solution(new String[]{"a", "a", "b", "a", "c", "d"}, new String[]{"a", "a", "a", "c", "d"}));
}

---

✍️ 정리

• 이름이 중복될 수 있기 때문에 단순히 contains나 indexOf로는 해결이 불가능합니다.
• 정렬 후 비교하거나 HashMap으로 개수를 추적하는 방식이 안정적입니다.
• 속도가 중요하다면 HashMap 방식을 추천합니다.