프로그래머스 완주하지 못한 선수(42576)

완주하지 못한 선수

1. 힌트

1) 동명이인이 있을 수 있기 때문에 Set을 이용해서 집합의 차집합을 구해내는 것으로는 풀 수 없다.

2) 이름 별로 몇 개가 있는지 세어서 비교해야 하는데 이 때 HashMap<String, Integer>을 사용할 수 있다.

2. 구현

그러나 XOR연산의 특징을 이용하면 이와 같이도 풀 수 있다.
XOR연산의 특징으로는 자기 자신과의 XOR값은 0이 된다는 것이고, 연산의 순서가 상관 없다는 것인데, 이를 이용하면 중복을 제거하는데 사용할 수 있다.

import java.util.*;

public class Solution {
    public String solution(String[] participant, String[] completion) {
        int x = 0;
        for (String p : participant) x ^= p.hashCode();
        for (String c : completion) x ^= c.hashCode();
        for (String p : participant)
            if (p.hashCode() == x) return p;
        return null;
    }
}

프로그래머스에서 채점은 통과하지만 사실 String의 hashCode() 구현에 따르면 서로 다른 문자열간에도 해시값의 충돌이 일어날 수 있다.

문제 입력 조건에는 맞지 않지만 그 예시
문자열의 길이가 15이상만 되어도 $26^{15}$는 64비트 정수형을 초월하기 때문에 비둘기집 원리에 따라 충돌이 무조건 발생할 수 밖에 없다.