🔔 답안만 쏙쏙 골라보고싶으신 분들께
풀이 과정과 접근 방법 없이, 문제에 대한 해설만 보고싶으시다면 접근3. 해시 | HashMap 으로 가주시기 바랍니다.
완주하지 못한 선수
📄 문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
🚫 제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
접근1. 차집합 | List.removeAll()
👁🗨 접근방식
new ArrayList(List.of(..)) 메서드를 통해, participant 와 completion 을 변할 수 있는 리스트 로 변경한다.
이후, 리스트의 차집합 메서드인 removeAll(..) 을 통해 participant 에 대한 completion 의 차집합을 구한다.
import java.util.ArrayList;
import java.util.List;
class Solution {
public String solution(String[] participant, String[] completion) {
List<String> p = new ArrayList<>(List.of(participant)); //p 를 participant로 초기화한다.
List<String> c = new ArrayList<>(List.of(completion)); //c 를 completion으로 초기화한다.
p.removeAll(c); //p 에서 c를 제거(차집합) 한다.
return p.get(0); //p 에서 제일 앞에 있는 원소를 반환한다. (어차피 p 와 c의 원소의 개수의 차는 1이므로 차집합도 하나밖에 나오지 않는다.)
}
}⛔ 발생한 문제
코드 실행 시, 3번 테스트케이스 에서 IndexOutOfBoundsException 이 발생한다 .
오류로그를 살펴보니, return p.get(0); 구문에서 해당 오류가 발생하는 것 같다.
3번 테스트케이스
| participant | completion | return |
|---|---|---|
| ["mislav", "stanko", "mislav", "ana"] | ["stanko", "ana", "mislav"] | "mislav" |
원인 탐색
p와c간의 차집합을 담은p의size가 0이다- 이유는
p와c간의 차집합이 존재하지 않아서 일 것 이다. - 이유는 차집합에서는 중복되는 요소또한 두 리스트에서 존재하면 모두 지워버리기 때문일 것 이다.
즉 p 에 있는 중복요소A,A'가 c에도 존재할경우,A혹은A'만 지우는것이 아닌A와A'둘 다 지우는 것이다. - 그렇다면, 3번 테스트 케이스에 있는
mislav라는 이름을 가진 두 동명이인 모두가 완주한것으로 보았을 것 이다.
다음 추론을 바탕으로 2번째 접근을 해보기로 하였다.
접근2. 차집합 구현 | c -> List::remove
👁🗨 접근방식
중복요소중 하나만 제거하는 차집합 로직을 구현한다.
completion 의 요소들을 을 iteration 하여, participant 에 있는 요소에서 제거한다. (completion 은 participant 의 부분집합이므로 completion 에 대한 participant 의 차집합은 공집합 이다.)
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
//remove 연산이 주를 이루므로 remove 메서드의 시간복잡도가 O(n) 인 ArrayList보단 O(1) 인 LinkedList 가 더 적합하다.
List<String> p = new LinkedList<>(Arrays.asList(participant));
Arrays.stream(completion).forEach(p::remove); //completion 의 요소를 iteration 하여 각 요소를 인자로 넣은 p 의 remove 메서드를 실행시킨다.
return p.get(0); //p 에서 제일 앞에 있는 원소를 반환한다. (어차피 p 와 c의 원소의 개수의 차는 1이므로 직접 구현한 차집합의 결과도 하나밖에 나오지 않는다.)
}
}⛔ 발생한 문제
제출 후 채점하기 시 효율성테스트를 모두 통과하지 못한다.
원인 탐색
new LinkedList<>(Arrays.asList(participant));의 시간복잡도가 높을 것 이다.- List 를 통한 추가/제거 가 아닌 다른 로직으로도 문제를 풀 수 있지 않을까?
다음 추론을 바탕으로 차집합이 아닌 새로운 로직을 고안해 3번째 접근을 해보기로 하였다.
접근3. 해시 | HashMap
👁🗨 접근방식
채 거르기 식 로직을 채택한다.
- 참여자의 이름을
KeyKey 에 해당하는 이름을 가진 참여자 수 (즉 해당 이름을 가지고있는 동명이인의 수) 를Value로 하는 HashMapmap을 만든다. - 이후, participant 의 요소들을 iteration 하여, 각 요소별 이름으로, map 에 put 한다(이때, value 는 기본적으로 1이지만, 이미 해당 이름을 key 값으로 가진 요소가 map 에 존재할경우, 해당 요소의 value 에 1을 더한값을 저장한다 ->
Value = Key가존재하는가 ? Value + 1 : 1) - 이후, completion 의 요소들을 iteration 하여, 각 요소별 이름으로 map 에 put 한다 (이때, value 는 기존 value 에서 1을 뺀 값을 저장한다.
Value = Value - 1) - 마지막으로, map 의 요소들을 iteration 하여, value 가 1 이상인 요소의 key 를 return 한다.
import java.util.HashMap;
import java.util.concurrent.atomic.AtomicReference;
public class Solution {
public String solution(String[] participant, String[] completion) {
HashMap<String, Integer> map = new HashMap<>();
for (String s : participant)
map.put(s, map.getOrDefault(s, 0) + 1);
for (String s : completion)
map.put(s, map.get(s) -1);
AtomicReference<String> answer = new AtomicReference<>();
map.forEach((k, v) -> {
if(v == 1) answer.set(k);
});
return answer.get();
}
}
결과
정확성 테스트 및 효율성 테스트를 전체 통과하였다
