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

프로그래머스 고득점 Kit: 해시 - 완주하지 못한 선수

문제 설명

"완주하지 못한 선수" 문제는 주어진 참가자 명단과 완주자 명단을 비교하여 완주하지 못한 선수를 찾는 문제입니다. 모든 선수들은 한 번만 참가하거나 완주합니다. 단, 완주하지 못한 선수는 단 한 명만 존재합니다.

문제 접근 방법

1. HashMap 사용: 각 선수의 이름을 키(key)로 하고, 해당 선수의 참가 횟수를 값(value)으로 하는 HashMap을 사용합니다.
2. 참가자 처리: 참가자 명단에서 각 선수의 이름을 키로 하여 참가 횟수를 카운트합니다.
3. 완주자 처리: 완주자 명단에서 각 선수의 이름을 키로 하여 참가 횟수를 감소시킵니다.
4. 완주하지 못한 선수 찾기: HashMap에서 값이 0이 아닌 선수를 찾습니다.

시간 복잡도 분석

• 참가자와 완주자 명단의 길이를 N이라고 할 때, 시간 복잡도는 O(N)입니다.
  • 참가자 명단을 처리하는데 O(N)
  • 완주자 명단을 처리하는데 O(N)
  • HashMap을 순회하는데 O(N)

따라서 전체 시간 복잡도는 O(N)입니다.

해결 방법

아래는 주어진 문제를 해결하는 Java 코드입니다:

package psg.고득점킷트.해시;

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

public class PSG_완주하지못한선수 {

    public static void main(String[] args) {
        PSG_완주하지못한선수 psg_완주하지못한선수 = new PSG_완주하지못한선수();
        String solution = psg_완주하지못한선수.solution(new String[]{"leo", "kiki", "eden"}, new String[]{"eden", "kiki"});
        System.out.println(solution);
    }

    // 선수 이름을 key로 map을 구성하며, 그곳에 숫자를 기록, 만약 0보다 큰 값이라면 그 사람은 완주하지 못한 것
    // 완주하지 못한 선수는 단 한 명
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();
        for (String pa : participant) {
            map.put(pa, map.getOrDefault(pa, 0) + 1);
        }
        for (String co : completion) {
            map.put(co, map.getOrDefault(co, 0) - 1);
        }
        for (String key : map.keySet()) {
            if (map.get(key) > 0) {
                return key;
            }
        }
        return "";
    }
}