문제
마라톤 참가자 목록 participant와 완주한 사람 목록 completion 이 주어진다.
이 중에서 완주하지 못한 선수 1명을 찾는 문제이다.
내가 작성한 답안
/**
* === 완주하지 못한 선수 ===
* [문제 요약]
* 마라톤 참가자 목록 paricipant와 완주한 사람 목록 completion 이 주어진다.
* 이 중에서 완주하지 못한 선수 1명을 찾는 문제이다.
*
* [조건]
* - 참가자 수: 최대 100,000
* - 동명이인 가능
*
* [이 문제의 핵심 알고리즘]
* - HashMap Counting
*
* [사고 과정]
* 1. 참가자 카운트 - leo(1), kiki(1), eden(1)
* 2. 완주자 제거 - eden, kiki
* leo : 1
* kiki : 0
* eden : 0
* => 남은 사람은 leo
*/
import java.util.*;
public class InCompleteRun {
public String solution(String[] participant, String[] completion) {
Map<String, Integer> map = new HashMap<>();
// 1. 참가자 등록 - 참가 선수 Map에 추가
// map.getOrDefault() - 참가자 카운트
for (String p : participant) {
map.put(p, map.getOrDefault(p, 0) + 1);
}
// 2. 완주자 제거 - 완주한 선수는 해당 map에서 제외
for (String c : completion) {
map.put(c, map.get(c) - 1);
}
// 3. 남은 사람 찾기 - 업데이트 된 map의 key를 순회해서 0보다 크면 return 해준다
for (String key : map.keySet()) {
if (map.get(key) > 0) {
return key;
}
}
return "";
}
}
Java
복사
문제 이해
입력
participant, completion
예시
participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]
Java
복사
출력
leo
Java
복사
제약조건
•
participant 최대 100,000
•
completion = participant - 1
•
동명이인 가능
알고리즘 설계
접근
•
participant에서 completion을 제거
•
하지만 O(N^2) → 100000이면 시간초과
정렬 전략
•
participant sort, completion sort
최적화 전략
HashMap Counting
참가자 count +
완주자 count -
남은 사람 = 완주하지 못한 사람
Java
복사
자료구조 선택
HashMap<String, Integer>
Java
복사
시간복잡도
O(N)
Hash + Sum 합 전략 (다른풀이)
•
참가자 hash 합
◦
모든 참가자의 hashCode() 값을 더한다.
•
완주자 hash 제거
◦
완주자의 hashCode() 값을 빼준다.
•
남은 hash 찾기
◦
남은 hash → 완주하지 못한 선수
알고리즘 흐름
hashSum = 참가자 hashCode 합
hashSum -= 완주자 hashCode
남은 hash = 완주하지 못한 선수
Java
복사
오늘의 진행내용 정리
[Day 4]
문제
완주하지 못한 선수
사용 알고리즘
해시맵 카운팅
사용한 자료구조
맵
시간복잡도
O(n)
배운 점
1. map.getOrDefault를 활용하여 key의 value를 증가시켜줄 수 있다.
2. map에 추가된 key를 map.get(c)을 활용하여 해당 map의 value를 감소시켜줄 수 있다.
3. 업데이트 된 map의 key를 순회 -> 0보다 크면 그 key가 곧 완주하지 못한 선수를 의미한다.
C
복사