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

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

velog 시작한 기념으로 프로그래머스 코딩테스트연습 가장 첫번째 문제 풀이를 올려본다.
participant보다 completion가 사람 한명만 적을때 걔(jack이라 하자)를 찾는 문제이다.

a. 가장 무난한 풀이는 Map으로 p에서 count 더했다가 c에서 빼는거다. 그다음에 Map iterate하면서 count 0인 jack을 찾는다. O(n)

b. 그런데 a번은 괜히 사람들 count까지 구해주니까 낭비인 느낌이 드네. p와 c를 합쳐놓고보면 jack 빼고는 다 짝수번 있다. 그러므로 Set에서 1번 나오면 add, 2번 나오면 remove, ... 홀수번 나오면 add, 짝수번 나오면 remove 하면 결국 Set에 jack 혼자 남는다. 역시 O(n)이지만 Map보다 살짝 가벼운 Set을 썼고 게다가 마지막에 Set크기가 1이므로 iterate가 없는 셈이다.

public String solution(String[] participant, String[] completion) {
        HashSet<String> s = new HashSet<String>(participant.length);
        for (String p : participant) {
            if (s.contains(p))
                s.remove(p);
            else
                s.add(p);
        }
        for (String p : completion) {
            if (s.contains(p))
                s.remove(p);
            else
                s.add(p);
        }
        for (String key : s)
            return key;
        return null;
    }

c. 홀짝으로 가면 생각나는게 xor bit 연산이다. 마침 문제에 보면 사람이름은 최대 20자이므로 char[20]만 가지고 각 자리수에 xor해가면 jack만 남는다. 역시 O(n)이지만 문제 카테고리와 다르게 Map, Set을 안썼으므로 미세하게나마 b번보다 빠를거다. (참고로 trim 안해주면 끝에 null들이 붙은 문자열이 나와서 fail)

public String solution(String[] participant, String[] completion) {
        char[] names = new char[20];
        for (String p : participant) {
            for (int i=0; i<p.length(); ++i)
                names[i] ^= p.charAt(i);
        }
        for (String p : completion) {
            for (int i=0; i<p.length(); ++i)
                names[i] ^= p.charAt(i);
        }
        return new String(names).trim();
    }

참고로 LeetCode에 xor 관련 주옥같은 문제들이 있다. Single Number 1~3