문제
문제는 링크를 참고하세요.
소스
소스는 깃허브에 올려두었습니다.
풀이
문제의 핵심은 participant 배열에는 존재하고 completion 배열에는 존재하지 않는 한명의 이름을 찾아내는 것
쉽게 생각할 수 있는 풀이 방법은 participant 배열에 들어있는 사람의 이름을 반복하면서 completion 에 있는 사람 이름이 존재하는지 검사하는 방법입니다.
문제점 - 검사방법
participant 배열을 반복하면서 지금 찾아야 되는 대상의 이름이 A 라고 가정하겠습니다. completion 배열을 반복하면서 A 라는 이름이 나오면 존재하는 것으로 생각할 수 있지만 그렇지 않습니다. 만약 A 라는 이름을 가진 사람이 2명이고 이 사람 중 한명이 마라톤을 완주하지 못했다고 가정하면 이 방법으로는 문제를 풀 수 없습니다. 왜냐면 처음 A를 검사 한 후에도 completion 배열에 A라는 이름을 포함하고 있기 때문입니다.
▶️ 위에서 A를 이미 한번 찾았지만 이후 A 를 또 찾은 것으로 판단
이런 단점을 보완하기 위해서 한명을 찾을 때 마다 하나씩 지워가는 방법(null 처리하는 방법)을 사용할 수 있습니다.
문제점 - 시간복잡도
다만, 이 방법에도 단점이 있습니다. 바로 시간복잡도인데요.
participant 의 크키가 n 이라고 가정하면 completion 는 n - 1 이 됩니다. 따라서 시간복잡도를 계산하면
O (n * (n - 1)) = O (n^2)
제곱 단위의 시간복잡도는 보통 좋지 않은 알고리즘으로 분류되기 때문에 다른 방법을 고민했습니다. 만약 completion 배열을 검사하는데에 시간복잡도가 O(1) 이 된다면 이 알고리즘은 다음과 같은 시간복잡도를 가질 수 있습니다.
O (n * 1) = O (n)
개선하기 - 적절한 자료구조 선택
조회에 시간복잡도 O (1) 을 가지는 자료형은 몇가지가 있습니다. 예를 들어서 ArrayList 를 조회할 때 시간복잡도가 O (1) 이고, HashMap 또한 조회 할 때 시간복잡도가 O (1) 입니다.
이 때 사람이름으로 조회할 때 시간복잡도가 O (1) 이어야 한다는 점에 주의해야 합니다. ArrayList 같은 경우 value 로 값을 찾을 때는 모든 배열을 하나하나 찾아봐야 하기 때문에 배열의 크기가 n 이라고 가정하면 O(n) 의 시간복잡도를 가집니다. 따라서, HashMap 을 사용하기로 했습니다.
participant 를 반복하면서 map 에 다음과 같은 형태로 값을 넣습니다.
이름 : 참가자수 (count)
즉, A 라는 사람이 마라톤 참여자 명단에 있다면 A 가 총 몇명 참가했는지 기록해두는 것이죠. 그리고 completion 를 반복하면서 해당 이름의 count 수를 하나씩 뺍니다. 이렇게 하면 최종적으로 count 가 1인 사람 1명이 마라톤을 완주하지 못한 사람이겠죠.
코드
public String solution(String[] participant, String[] completion) {
// map 에서 사용할 수 있는 공간을 넘기려는 경우 크기 확장이 일어나는데, 이 때 연산의 비용이 크므로 초기 공간을 설정해주는 것이 좋다
// 로드팩터가 1이 아니기 때문에 1번 정도는 공간 확장이 일어날 수 있지만, 뭐 1번 정도야..
Map<String, Integer> map = new HashMap(participant.length);
// 참가자 count
for (String p : participant) {
map.put(p, map.getOrDefault(p, Integer.valueOf(0)) + 1);
}
// 완주자 체크
for (String c : completion) {
map.put(c, map.get(c) - 1);
}
// count 가 1인 사람이 완주하지 못한 사람
Integer one = 1;
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (one.equals(entry.getValue())) {
return entry.getKey();
}
}
return null;
}.jpeg)